In socially monogamous species, in which both sexes provide essential parental care, males as well as females are expected to be choosy. Whereas hundreds of studies have examined monogamy in biparental birds, only several such studies exist in fish. We examined mate choice in the biparental, colonial cichlid fish Neolamprologus caudopunctatus in Lake Tanganyika, Zambia. We genotyped more than 350 individuals at 11 microsatellite loci to investigate their mating system. We found no extrapair paternity, identifying this biparental fish as genetically monogamous. Breeders paired randomly according to their genetic similarity, suggesting a lack of selection against inbreeding avoidance. We further found that breeders paired assortatively by body size, a criterion of quality in fish, suggesting mutual mate choice. In a subsequent mate preference test in an aquarium setup, females showed a strong preference for male size by laying eggs near the larger of 2 males in 13 of 14 trials.