A focus on pair bonds between males and females is fundamental to study the evolution of social organization. Because pair bonds are generally identified from direct observations of pairs that maintain physical proximity, pair bonds may have been overlooked in animals that do not exhibit such visible pairs. The Lake Tanganyika cichlid fish Xenotilapia rotundiventralis forms schools that consist of mouthbrooding and non-brooding adults in mid-water, and visible pairs are not recognized. A previous study suggested that mouthbrooding females transfer fractions of the young to males when the young become large. However, it remains a mystery whether the mating pairs maintain pair bonds so that the females can transfer the young to their mates. To answer this question, we conducted a parentage analysis using 10 microsatellite markers. The analysis showed that the mouthbrooding adults were most likely genetic fathers and mothers of the young in their mouths. This finding suggests that the female-to-male shift of young takes place between mating partners, and thus the mating pairs maintain pair bonds at least until the shift of young. The present study is the first to detect pair bonds in animals in which physical proximity has not been observed.