Many animals exhibit size-assortative mating where reproductive pairs are more similar in size than expected through random mating.  Matching theory predicts this occurs because both males and females prefer and will leave existing partners for bigger mates.  Monogamous pairing and size-assortative mating has been described for coral reef fishes, but the underlying behavioural 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 mouthbrooding coral reef cardinalfish Sphaeramia nematoptera.  For 65 pairs observed over a 23 month period, there was a strong correlation between male and female size.  This size assortative mating was not incidental through growing up together, since only 28% of juvenile pairs were still found together after four months, and only 7% after eight months.  For those changing partners over this period, there was a strong correlation between the sizes of individuals and their new partners, with individuals only ever leaving partners for larger mates.  We experimentally removed 16 males and 18 female partners from existing pairs to examine the role of male and female mate preferences in leading to size-assortative mating.  The strong positive relationship between the sizes of male and female partners was maintained as individuals found new partners.  Both females and males chose similar sized partners after both natural losses and following mate removal, indicating both sexes exhibit a mutual preference for partners of near similar size.  We suggest that monogamous pairing occurs in cardinalfish because mouthbrooding restricts multiple mating by males. Size assortative pairing follows as larger males 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.