Many vertebrates form monogamous pairs to mate and care for their offspring. However, genetic tools have increasingly shown that many offspring arise from matings outside of the monogamous pair bond. Social monogamy is relatively common in coral reef fishes, but there have been relatively few studies that have confirmed monogamy or extra-pair reproduction, either for males or females. Here long-term observations and genetic tools were applied to examine the parentage of embryos in a paternally mouthbrooding cardinalfish, Sphaeramia nematoptera. Paternal care in fishes, such as mouth brooding, is thought to be associated with a high degree of confidence in paternity. Two-years of observations confirmed that S. nematoptera form long-term pair bonds within larger groups. However, genetic parentage revealed extra-pair mating by both sexes. Of 105 broods analysed from 64 males, 30.1% were mothered by a female that was not the partner and 11.5% of broods included eggs from two females. Despite the high paternal investment associated with mouthbrooding, 7.5% of broods were fertilised by two males. Extra-pair matings appeared to be opportunistic encounters with individuals from outside the immediate group. We argue that while pair formation contributes to group cohesion, both males and females can maximise lifetime reproductive success by taking advantage of extra-pair mating opportunities. The results contradict the theory that paternal care is associated with a high confidence in paternity.