The Southern Hemisphere graylings (Prototroctidae) comprise two modern species; the extinct New Zealand grayling (Prototroctes oxyrhynchus) and the extant Australian Grayling (P. maraena). The New Zealand grayling was formerly described as one of the most common New Zealand freshwater fish, but has not been recorded since the 1920s. Approximately 20 preserved specimens are held in museums. The Australian grayling, native to south eastern Australian coastal catchments, has declined since European settlement, and is listed as vulnerable. The two species are morphologically very similar, and presumably had a similar biology, however the genetic relationship between the two species is unstudied. We sampled Australian Grayling from Tasmania and extinct grayling from New Zealand, encompassing the geographic distribution of the species. Using genetic techniques specific to formalin preserved specimens, we obtained partial mitochondrial cytochrome b sequence from the New Zealand grayling. Phylogenetic analysis indicates a strongly supported sister relationship between the Australian and New Zealand grayling. The level of divergence (~8%) supports separate species status and indicates a divergence time during the Pliocene around 4 million years ago, and the possibility of multiple colonisation events of New Zealand when fossil taxa are taken into consideration (e.g. 16-19 Mya Saint Bathans Grayling taxa).