To investigate the role of vicariance and dispersal on New Zealand’s estuarine biodiversity, we examined variability in mitochondrial cytochrome c oxidase I (COI) gene sequences for the amphipod genus Paracorophium. Individuals from the two nominate endemic species (P. excavatum and P. lucasi) were collected from sites throughout the North and South Islands. Sequence divergences of 12.8% were detected among the species. However, divergences of up to 11.7% were also observed between well supported clades, suggesting the possibility of cryptic species. Nested clade analyses identified four distinct lineages from within both P. excavatum and P. lucasi, with boundaries between clades corresponding to topographical features (e.g. Cook Straight, North and East Cape). Sequence divergences of 3.7 - 4.9% were also observed within geographic regions (e.g. east and west coasts of the upper North Island). Genetic structure in Paracorophium appears to represent prolonged isolation and allopatric evolutionary processes dating back to the Upper Miocene and continuing through the Pliocene and early Pleistocene. Based on molecular clock estimates from sequence divergences and reconstructions of New Zealand’s geological past, we suggest that sea level and landmass changes during the early Pleistocene (2 Mya) resulted in the isolation of previously contiguous populations leading to the present-day patterns. COI genetic structure was largely congruent with previously observed allozyme patterns and highlights the utility of COI as an appropriate marker for phylogeographic studies of the New Zealand estuarine fauna.