Freshwater systems are naturally fragmented and heterogeneous habitats that promote genetic sub-division and speciation for aquatic biota. Here we provide a novel nuclear genetic perspective (49 allozyme loci) complimented with updated mitochondrial data for the eleotrid genus Philypnodon to investigate broad genetic sub-structure across south-eastern Australia as a foundation for management and conservation. The genus is nominally comprised of two small benthic fishes with contrasting physical and ecological traits, namely the Flathead Gudgeon P. grandiceps and the Dwarf Flathead Gudgeon P. macrostomus. Extensive sample coverage included 99 sites across 5 major drainage divisions and 48 river basins. Nuclear markers revealed strong, geographically-based divergence and sub-structure, contrasting with shallower but largely congruent patterns for mtDNA. The results flag that each nominal species represents a hyper-cryptic species complex, including both broadly distributed and narrow-range taxa, with complicated biogeographic patterns. Predictions on dispersal and genetic structure based on ecological traits were only partially supported and varied by region, with the potential signature of human-assisted translocation evident in several catchments. Further intensive sampling in an important area of high genetic diversity, coastal south-east Queensland, is recommended to better resolve species boundaries and conservation units. The findings provide new insights on regional ecology and biogeography, demonstrating that even supposedly common species can, in reality, have complex conservation and management needs.