The annual killifishes of the genus Cynolebias include one well supported clade composed of three taxa: Cynolebias adloffi, from Porto Alegre (southern Brazil), C. cf. adloffi and Cynolebias viarius, parapatrically distributed in southeastern Uruguay. Cynolebias cf. adloffi has always been considered an intergradation complex of populations between C. adloffi and C. viarius showing high levels of morphological variability and its systematic affinities have been historically discussed. This study clarified the patterns of genetic differentiation of C. cf. adloffi by means of RAPD markers to define its taxonomic status as a possible separated taxon. Multidimensional scaling analysis reveals that C. cf. adloffi is composed of two highly structured genetic groups (northern and southern) with discrete geographical distributions. The estimate of gene diversity for RAPD markers could suggest a scenario in which the rainy season flood pool populations across large distances could make intrapopulation variation high but interpopulation variation low. Phylogenetic analyses (UPGMA and parsimony) show different and unstable patterns of relationships among the taxa analyzed. In the UPGMA tree, C. viarius and C. cf. adloffi appear as sister taxa, while parsimony analysis does not support a unique hypothesis of relationship. Our analyses are in agreement with the hypothesis that C. cf. adloffi may well be a case of ancient hybrid ancestry followed by its divergence associated with Pleistocene and post-Pleistocene environmental changes in this region.