Many animals exhibit size-assortative mating, and matching theory predicts this occurs because both males and females prefer bigger mates. Monogamy and size-assortative pairing have been described for coral reef fishes, but the underlying behavioral mechanism has not been tested. Here, we took a long-term observational and experimental study to resolve the causes of size-based pairing in the paternal mouthbrooding coral reef cardinalfish Sphaeramia nematoptera. For 65 pairs observed over a 23-month period, there was a strong size-correlation between paired males and females. This size-assortative mating was not a consequence of pairing at a young age as re-pairing was common, with only 7% juvenile pairs still found together after 8 months. For adults that changed partners over this period, there was a strong correlation between the size of individuals and the size of their new partners. Following experimental removal of partners, both males and females quickly repaired with partners of similar or larger size. Together, these results suggest that size-assortative mating is explained by a mutual preference by both males and females for larger mates. We suggest that monogamous pairing occurs in cardinalfish because mouthbrooding restricts multiple mating by males. Size-assortative pairing follows as larger males likely prefer the more fecund larger females, and larger females prefer larger males because they can successfully brood all of their eggs. Mutual mate choice will likely explain size-assortative pairing in other fish species with paternal care.