Female aggregation and male territoriality are considered to be hallmarks of polygynous mating systems. The development of genetic parentage assignment has called into question the accuracy of behavioral traits in predicting true mating systems. In this study we use 14 microsatellite markers to explore the mating system of one of the most behaviorally polygynous species, the California sea lion (Zalophus californianus). We sampled a total of 158 female-pup pairs and 99 territorial males across two breeding rookeries (San Jorge and Los Islotes) in the Gulf of California, Mexico. Fathers could be identified for 30% of pups sampled at San Jorge across three breeding seasons and 15% of sampled pups at Los Islotes across two breeding seasons. Analysis of paternal relatedness between the pups for which no fathers were identified (sampled over four breeding seasons at San Jorge and two at Los Islotes) revealed that few pups were likely to share a father. Thirty-one percent of the sampled males on San Jorge and 15% of the sampled males on Los Islotes were assigned at least one paternity. With one exception, no male was identified as the father of more than two pups. Furthermore, at Los Islotes rookery there were significantly fewer pups assigned paternity than expected given the pool of sampled males (p<0.0001). Overall, we found considerably lower variation in male reproductive success than expected in a species that exhibits behavior associated with strongly polygynous mating. Low variation in male reproductive success may result from heightened mobility among receptive females in the Gulf of California, which reduces the ability of males to monopolize groups of females. Our results raise important questions regarding the adaptive role of territoriality and the potential for alternative mating tactics in this species.