Determining the extent of variation in male mating strategies and reproductive success is necessary to understand the fitness benefits of social and cooperative behaviour. This study assesses the reproductive success of male Indo-Pacific bottlenose dolphins in a small embayment population where different behavioural strategies of males have previously been identified. Parentage for 44 sampled calves was examined using 23 microsatellite loci and one mitochondrial DNA marker. Our candidate parent pool of 70 males and 64 females contained individuals sampled from both the embayment and adjacent coastal populations. A moderate level of polygyny was detected in our sample. We assigned paternity of 23 calves to 12 males at the strict 95% confidence level and an additional nine calves to two males at the 80% confidence level. The majority (92%) of successful males were identified as residents to the embayment, and 46% of offspring were located within the same social group or community as their father. Our results suggest that the size of alliances was the best predictor of reproductive success for males in this population, while the strength of association among allied males, alliance stability and male ranging patterns had little influence. In line with predictions for male alliances formed between unrelated individuals, we found that reproductive skew within alliances was not large. Together, our genetic and behavioural analyses demonstrate that alliance formation between male dolphins is a successful strategy to enhance reproductive output.