With examples from Australo-Papuan ornithology, we examine the technical and theoretical roots of molecular phylogeography and review its development. We describe the progression from ad hoc interpretation of gene trees in single species phylogeographic studies through to comparative phylogeography and currently advocated model-testing approaches. Mitochondrial DNA (mtDNA) sequences have provided most advances to date, although we demonstrate and advocate the future use of multilocus datasets analysed with coalescent methods. We examine interrelationships among speciation research, historical biogeography, phylogeography and landscape genetics. Mitochondrial paraphyly, in which individuals of one species or population have mtDNA that is more closely related to that of another than to their own, emerges in 44% of Australian studies to date as a common, important result in Australian avian phylogeography. Accordingly, we explore at length its most common causes and its impact on case studies in Australo-Papuan avian phylogeography. The impact of so much paraphyly on avian phylogeography and taxonomy is a major theme of the review. We suggest a full research agenda for avian phylogeography in the Australo-Papuan region that spans diverse topics: the need for more studies of pelagic birds, spatio-temporal links between New Guinea and Australia, island populations, testing of long-established biogeographical hypotheses, and integration of molecular and non-molecular datasets into integrated evolutionary understanding of species and populations. Studying the full continuum of divergences from landscape genetics, to phylogeography, to recently diverged species with evidence of paraphyly, to highly divergent species with many fixed differences will lead to a more complete understanding of the processes and patterns of avian evolution.