Patterns of genetic connectivity are increasingly considered in the design of marine protected areas (MPAs) in both shallow and deep water. In the New Zealand Exclusive Economic Zone (EEZ), deep-sea communities at upper bathyal depths (<2000 m) are vulnerable to anthropogenic disturbance from fishing and potential mining operations. Currently, patterns of genetic connectivity among deep-sea populations throughout New Zealand's EEZ are not well understood. Using the mitochondrial Cytochrome Oxidase I and 16S rRNA genes as genetic markers, this study aimed to elucidate patterns of genetic connectivity among populations of two common benthic invertebrates with contrasting life history strategies. Populations of the squat lobster Munida gracilis and the polychaete Hyalinoecia longibranchiata were sampled from continental slope, seamount, and offshore rise habitats on the Chatham Rise, Hikurangi Margin, and Challenger Plateau. For the polychaete, significant population structure was detected among distinct populations on the Chatham Rise, the Hikurangi Margin, and the Challenger Plateau. Significant genetic differences existed between slope and seamount populations on the Hikurangi Margin, as did evidence of population differentiation between the northeast and southwest parts of the Chatham Rise. In contrast, no significant population structure was detected across the study area for the squat lobster. Patterns of genetic connectivity in Hyalinoecia longibranchiata are likely influenced by a number of factors including current regimes that operate on varying spatial and temporal scales to produce potential barriers to dispersal. The striking difference in population structure between species can be attributed to differences in life history strategies. The results of this study are discussed in the context of existing conservation areas that are intended to manage anthropogenic threats to deep-sea benthic communities in the New Zealand region.