The freshwater fauna of Southern Australia is primarily restricted to the southwestern and southeastern corners of the continent, and is separated by a large, arid region that is inhospitable to this biota. This geographic phenomenon has attracted considerable interest from biogeographers looking to explain evolutionary diversification in this region. Here, we employed phylogenetic and phylogeographic approaches to evaluate the effect of this barrier on a group of four galaxiid fish species (Galaxiella) endemic to temperate Southern Australia. We also tested if continental shelf width has influenced connectivity among populations during low sea levels when rivers, now isolated, could have been connected. We addressed these questions by sampling each species across its range using multiple molecular markers (mitochondrial cytochrome b sequences, nuclear S7 intron sequences, and 49 allozyme loci). These data also allowed us to assess species boundaries, to refine phylogenetic affinities, and to estimate species ages. Interestingly, we found compelling evidence for cryptic species in G. pusilla, manifesting as allopatric eastern and western taxa. Our combined phylogeny and dating analysis point to an origin for the genus dating to the early Cenozoic, with three of the four species originating during the Oligocene-Miocene. Each Galaxiella species showed high levels of genetic divergences between all but the most proximate populations. Despite extensive drainage connections during recent low sea levels in southeastern Australia, populations of both species within G. pusilla maintained high levels of genetic structure. All populations experienced Late Pleistocene-Holocene population growth, possibly in response to the relaxation of arid conditions after the last glacial maximum. High levels of genetic divergence and the discovery of new cryptic species have important implications for the conservation of this already threatened group of freshwater species.