Whole-genome surveys of genetic diversity and geographic variation often yield unexpected discoveries of novel structural variation, which long-read DNA sequencing can help clarify. Here, we report on whole-genome phylogeography of a bird exhibiting classic vicariant geographies across Australia and New Guinea, the blue-faced honeyeater (Entomyzon cyanotis), and the discovery and characterization of a novel neo-Z chromosome by long-read sequencing. Using short-read genome-wide SNPs, we inferred population divergence events within E. cyanotis across the Carpentarian and other biogeographic barriers during the Pleistocene (~0.3–1.7 Ma). Evidence for introgression between nonsister populations supports a hypothesis of reticulate evolution around a triad of dynamic barriers around Pleistocene Lake Carpentaria between Australia and New Guinea. During this phylogeographic survey, we discovered a large (134 Mbp) neo-Z chromosome and we explored its diversity, divergence and introgression landscape. We show that, as in some sylvioid passerine birds, a fusion occurred between chromosome 5 and the Z chromosome to form a neo-Z chromosome; and in E. cyanotis, the ancestral pseudoautosomal region (PAR) appears nonrecombinant between Z and W, along with most of the fused chromosome 5. The added recombination-suppressed portion of the neo-Z (~37.2 Mbp) displays reduced diversity and faster population genetic differentiation compared with the ancestral-Z. Yet, the new PAR (~17.4 Mbp) shows elevated diversity and reduced differentiation compared to autosomes, potentially resulting from introgression. In our case, long-read sequencing helped clarify the genomic landscape of population divergence on autosomes and sex chromosomes in a species where prior knowledge of genome structure was still incomplete.