The evolutionary significance of spatial habitat gaps has been well recognized since Alfred Russel Wallace compared the faunas of Bali and Lombok. Gaps between islands influence population structuring of some species, and flightless birds are expected to show strong partitioning even where habitat gaps are narrow. We examined the population structure of the most numerous living flightless land bird in New Zealand, Weka (Gallirallus australis). We surveyed Weka and their feather lice in native and introduced populations using genetic data gathered from DNA sequences of mitochondrial genes and nuclear β-fibrinogen and five microsatellite loci. We found low genetic diversity among extant Weka population samples. Two genetic clusters were evident in the mtDNA from Weka and their lice, but partitioning at nuclear loci was less abrupt. Many formerly recognized subspecies/species were not supported; instead, we infer one subspecies for each of the two main New Zealand islands. Although currently range restricted, North Island Weka have higher mtDNA diversity than the more wide-ranging southern Weka. Mismatch and neutrality statistics indicate North Island Weka experienced rapid and recent population reduction, while South Island Weka display the signature of recent expansion. Similar haplotype data from a widespread flying relative of Weka and other New Zealand birds revealed instances of North Island—South Island partitioning associated with a narrow habitat gap (Cook Strait). However, contrasting patterns indicate priority effects and other ecological factors have a strong influence on spatial exchange at this scale.