Devonian rhizodontid fishes from East Gondwana include Gooloogongia loomesi Johanson & Ahlberg 1998 from near Canowindra, New South Wales (NSW), Australia and Aztecia mahalae gen. nov., sp. nov. from southern Victoria Land, Antarctica. Gooloogongia loomesi is known from well-preserved cranial and postcranial material, and as such represents the most complete rhizodont known. Newly discovered elements (braincase, pelvic girdle) are described for the first time. Aztecia mahalae gen. nov., sp. nov. is based on shoulder girdle material formerly assigned to Notorhizodon Young et al. 1992, which, based on skull and lower jaw morphology, is a member of the Tristichopteridae. The presence of several plesiomorphic characters suggests that Gooloogongia occupies a basal phylogenetic position within the Rhizodontida, while Aztecia n. gen. possesses a more derived shoulder girdle. We argue that the Rhizodontida evolved on the Gondwanan landmass. Notorhizodon occupies a relatively derived position within the Tristichopteridae, but is contemporary with the earliest and phylogenetically most basal Laurussian members of the group. This shows that the tristichopterids achieved a worldwide distribution considerably earlier than previously thought.