To date no complete phylogeny of all of the currently recognised Indo-Australian varanid species and subspecies has been published. This paper presents a comprehensive mitochondrial gene phylogeny of these lizards. A portion of the mitochondrial genome comprising part of the ND4 gene and three adjacent tRNA genes (hereafter referred to as ND4) was analysed alone and, for a subset of the taxa, combined with previously published mitochondrial data. Similar tree topologies were produced by both datasets although combining the data helped resolve some of the unresolved or weakly supported nodes in the ND4 analyses. The monophyly of the Indo-Australian group was strongly supported in all analyses. This group comprised three major lineages: the gouldii group, the Odatria group and the varius group. Mitochondrial ND4 nucleotide sequences were successfully amplified from all of the Indo-Australian monitor species and subspecies currently recognised and, as such, is the first comprehensive phylogenetic study of the Australian monitor lizards published. Analysis of the tempo of diversification and evolution of preferred habitat use identified six episodes of increased net speciation rate, with two closely adjacent episodes showing the highest rates of diversification and correlating with the appearance of all preferred habitat types. The comprehensive molecular phylogenetic framework will also be useful for the identification of varanid species and traded products derived from monitors and, as such, has important applications for wildlife management and conservation.