Contrasting evolutionary histories may be revealed by mitochondrial and nuclear information. Divergent New Guinean and eastern and western Australian lineages of Hephaestus fuliginosus (sooty grunter) were detected using mitochondrial data, with the extent of divergence consistent with cryptic speciation events. However, this phylogeographic pattern was not supported by nuclear gene data, and evidence for cryptic speciation appears driven almost entirely by introgression between H. fuliginosus and congeners on the periphery of its distribution (e.g. with H. tulliensis, H. jenkinsi or H. roemeri). Hephaestus fuliginosus is a single species with a complex evolutionary history. Introgression on the eastern coast is consistent with transfer of the mitochondrial genome of the resident species (H. tulliensis) to the invading species (H. fuliginosus) and may have provided the metabolic capacity for H. fuliginosus to spread into the cooler rainforest environment of the Wet Tropics region. Mitochondrial and nuclear analyses both identified the genus Hephaestus as polyphyletic with H. carbo and H. habbemai placed in a clade with Leiopotherapon unicolor and Amniataba percoides. The present study demonstrated the need to consider a variety of genetic information when assessing species identity in a widespread species and the need for a systematic revision of the genus and family as a whole.