The mayfly genus Austrophlebioides Campbell & Suter, 1988 is endemic to Australia and is widely distributed in eastern Australia and Tasmania. Here, the phylogenetic relationships among species of Austrophlebioides are investigated using cladistic analyses based on morphological characters of the nymph and adult, and the first phylogenetic hypothesis for the genus is presented. The results from the phylogenetic analyses support the recognition of three monophyletic species-groups: the ‘rieki’, ‘pusillus’ and ‘marchanti’ clades. The ‘pusillus’ clade is the sister-group to the ‘rieki’ clade, and the clade comprising these two groups is sister to the ‘marchanti’ clade. Minimal overlap was observed in the geographic distribution of the three Austrophlebioides clades. The ‘rieki’ clade is confined to the Wet Tropics bioregion of north-eastern Queensland. The ‘pusillus’ clade is distributed from central-eastern Queensland to Victoria. The ‘marchanti’ clade occurs in southern New South Wales, Victoria and Tasmania. Distributional limits of the three clades correspond with the presence of recognised biogeographic barriers (Burdekin Gap, Hunter Valley and Bass Strait) suggesting that vicariance has been important in the differentiation of the group and in determining present-day distributions of species.