Multilocus phylogeography can uncover taxonomically unrecognized lineage diversity across complex biomes. The Australian monsoonal tropics includes vast, ecologically intact savanna-woodland plains interspersed with ancient sandstone uplands. Though recognized in general for its high species richness and endemism, the biodiversity of the region remains underexplored due to its remoteness. This is despite a high rate of ongoing species discovery, especially in wetter regions and for rock-restricted taxa. To provide a baseline for ongoing comparative analyses, we tested for phylogeographic structure in an ecologically generalized and widespread taxon, the gecko Heteronotia binoei. We apply coalescent analyses to multilocus sequence data (mitochondrial DNA and eight nuclear DNA introns) from individuals sampled extensively and at fine scale across the region. The results demonstrate surprisingly deep and geographically nested lineage diversity. Several intraspecific clades previously shown to be endemic to the region were themselves found to contain multiple, short-range lineages. To infer landscapes with concentrations of unique phylogeographic diversity, we probabilistically estimate the ranges of lineages from point data and then, combining these estimates with the nDNA species tree, estimate phyloendemism across the region. Highest levels of phyloendemism occur in northern Top End, especially on islands, across the topographically complex Arnhem escarpment, and across the sandstone ranges of the western Gulf region. These results drive home that deep phylogeographic structure is prevalent in tropical low-dispersal taxa, even ones that are ubiquitous across geography and habitats.