Androdioecy (the coexistence of males and hermaphrodites) is considered a transitional state derived from pure hermaphroditism or dioecy, but the processes selecting for this rare breeding system are unclear, particularly in animals. In androdioecious species, the proportion of males in relation to hermaphrodites is usually so reduced that it is not known whether there is scope for mate choice, particularly when simultaneous hermaphrodites can self-fertilize. We investigated the potential role of male mate choice in the persistence of androdioecy in animals using a self-fertilizing androdioecious fish (Kryptolebias marmoratus) as a model. Hermaphrodites preferred to associate with males but showed no preference based on genetic similarity. In contrast, males displayed a strong preference for genetically dissimilar hermaphrodites, based, apparently, on olfactory cues. We suggest that disassortative male mate choice could be a critical factor in stabilizing androdioecy in cases where high selfing rates are associated with inbreeding depression.