Although most vertebrates reproduce sexually, a small number of fishes, amphibians and reptiles are known in which reproduction is asexual, i.e. without meiotic recombination. In fishes, these so-called unisexual lineages usually comprise only females and utilize co-occurring males of a related sexual species to reproduce via gynogenesis or hybridogenesis. Here, we examine patterns of microsatellite and mitochondrial DNA (mtDNA) variation in a widespread group of freshwater fishes (carp gudgeons; Hypseleotris spp.) to investigate a long-standing proposal that this group includes unisexual forms. We show that the mtDNA genome of most carp gudgeons in tributaries of the Goulburn River belongs to one of two deeply divided clades (∼10% cyt b divergence) and that nuclear variation divides the same individuals into four distinct groups. Group 1 exhibits the genotypic proportions of a random mating population and has a 1:1 sex ratio. Two other groups are extremely sex-biased (98% male, 96% female), exhibit excess heterozygosity at most loci and share at least one allele per locus with group 1. We propose that these two groups represent 'unisexual' hybridogenetic lineages and that both utilize co-occurring group 1 as sexual host. Interestingly, the fourth distinct group appears to represent hybrid offspring of the two putative hybridogenetic lineages. The propagation of clonal haploid genomes by both males and females and the ability of these clones to unite and form sexually mature diploid hybrid offspring may represent a novel mechanism that contributes to the dynamics of coexistence between hybridogenetic lineages and their sexual hosts.