Highly polymorphic single tandem repeat loci (STR, also known as microsatellite loci) remain a familiar, cost efficient class of markers for genetic analyses in ecology, behavior and conservation. We characterize a new universal set of ten STR loci (from 28 potential candidate loci) in seven baleen whale species, which are optimized for PCR amplification in two multiplex reactions along with a Y chromosome marker for sex determination. The optimized, universal set of STR loci provides an ideal starting point for new studies in baleen whales aimed at individual-based and population genetic studies, and facilitates data sharing among research groups. Data from the new STR loci were combined with genotypes from other published STR loci to assess the power to assign parentage (paternity) using exclusion in four species: fin whales, humpback whales, blue whales and bowhead whales. We argue that parentage studies should present a power analysis to demonstrate that the specific data are sufficiently informative to assign parentage with statistical rigor.