In polygynous species, males appear to gain additional offspring by pairing with multiple females simultaneously. However, this may not be true if some females copulate outside of the social pair bond. Polygynous males could experience lower paternity because of trade-offs among gaining multiple social mates, guarding fertility with these mates, and pursuing extra-pair matings. Alternatively, polygynous males could simultaneously gain extra social mates and have high paternity, either because of female preferences or because of male competitive attributes. We tested four predictions stemming from these hypotheses in a facultatively polygynous songbird, the dickcissel (Spiza americana). Unlike most previous studies, we found that males with higher social mating success (harem size) also tended to have higher within-pair paternity and that the number of extra-pair young a male sired increased significantly with his social mating success. Females that paired with mated males were not more likely to produce extra-pair young. In contrast, extra-pair paternity was significantly lower in the nests of females whose nesting activity overlapped that of another female on the same territory. This pattern of mating was robust to differences in breeding density. Indeed, breeding density had no effect on either extra-pair mating or on the association between polygyny and paternity. Finally, nest survival increased with harem size. This result, combined with the positive association between polygyny and paternity, contributed to significantly higher realized reproductive success by polygynous male dickcissels.