Extra-pair paternity within socially monogamous mating systems is well-studied in birds and mammals but rather neglected in other animal taxa. In fishes, social monogamy has evolved several times but few studies have investigated the extent to which pair-bonded male fish lose fertilizations to cuckolders and gain extra-pair fertilizations themselves. We address this gap and present genetic paternity data collected from a wild population of Variabilichromis moorii, a socially monogamous African cichlid with biparental care of offspring. We show that brood-tending, pair-bonded males suffer exceptionally high paternity losses, siring only 63% of the offspring produced by their female partners on average. The number of cuckolders per brood ranged up to nine and yet, surprisingly, brood-tending males in the population were rarely the culprits. Brood-tending males sired very few extra-pair offspring, despite breeding in close proximity to one another. While unpaired males were largely responsible for the cuckoldry, pair-bonded males still enjoyed higher fertilization success than individual unpaired males. We discuss these results in the context of ecological and phenotypic constraints on cuckoldry and the fitness payoffs of alternative male tactics. Our study provides new insights into how pair-bonded males handle the trade-off between securing within-pair and extra-pair reproduction.