Intraspecific variability in mating behavior and disparities between social and reproductive behavior add complexity to the description of animal mating systems. A previously published field study on a population of the maternally mouthbrooding cichlid fish Ctenochromis horei in the north of Lake Tanganyika suggested mate monopolization by the most dominant male. In the present study, genetic reconstructions of paternity in a population in the south of the lake provided no evidence for male mate monopolization, as none of the inferred sires had offspring in more than one brood. The ability to reconstruct sire genotypes from offspring alleles was confirmed by computer simulations. Multiple paternity occurred in several broods and was significantly more frequent in the sample taken in the rainy season than in the dry season sample (100% of broods versus 12.5%, respectively; p = 0.0014). The data suggest geographic and temporal variation in the mating behavior of C. horei despite its continuous year-round reproduction, invariable brood care behavior and habitat-specific distribution in the relatively constant and confined environment of a tropical lake. Moreover, our data show that inferences on the distribution of male reproductive success, if based on each geographical or temporal data set alone, would fail to describe the potential for sexual selection in this species.