Divergent selection between ecologically dissimilar habitats promotes local adaptation, which can lead to reproductive isolation (RI). Populations in the Poecilia mexicana species complex have independently adapted to toxic hydrogen sulfide and show varying degrees of RI. Here, we examined the variation in the mate choice component of prezygotic RI. Mate choice tests across drainages (with stimulus males from another drainage) suggest that specific features of the males coupled with a general female preference for yellow color patterns explain the observed variation. Analyses of male body coloration identified the intensity of yellow fin coloration as a strong candidate to explain this pattern, and common-garden rearing suggested heritable population differences. Male sexual ornamentation apparently evolved differently across sulfide-adapted populations, for example because of differences in natural counterselection via predation. The ubiquitous preference for yellow color ornaments in poeciliid females likely undermines the emergence of strong RI, as female discrimination in favor of own males becomes weaker when yellow fin coloration in the respective sulfide ecotype increases. Our study illustrates the complexity of the (partly non-parallel) pathways to divergence among replicated ecological gradients. We suggest that future work should identify the genomic loci involved in the pattern reported here, making use of the increasing genomic and transcriptomic datasets available for our study system.