Polyandry-induced sperm competition is assumed to impose costs on males through reduced per capita paternity success. In contrast, studies focusing on the consequences of polyandry for females report increased oviposition rates and fertility. For these species, there is potential for the increased female fecundity associated with polyandry to offset the costs to males of shared paternity. We tested this hypothesis by comparing the proportion and number of offspring sired by males mated with monandrous and polyandrous females in the hide beetle, Dermestes maculates, both for males mating with different females and for males remating with the same female. In 4 mating treatments, monandrous females mated either once or twice with the same male and polyandrous females mated either twice with 2 different males or thrice with 2 males (where 1 male mated twice). Polyandrous and twice-mating monandrous females displayed greater fecundity and fertility than singly mating monandrous females. Moreover, males remated to the same female had greater paternity regardless of whether that female mated with another male. In both polyandrous treatments, male mating order did not affect paternity success. Finally, although the proportion of eggs sired decreased if a male mated with a polyandrous female, multiply mating females or females that remated with a previous mate laid significantly more eggs and thus the actual number of eggs sired was comparable. Thus, males do not necessarily accrue a net fitness loss when mating with polyandrous females. This may explain the absence of any obvious defensive paternity-protection traits in hide beetles and other species.