Dramatic local population decline brought about by anthropogenic-driven change is an increasingly common threat to biodiversity. Seabird life history traits that make them particularly vulnerable to such change, therefore understanding population connectivity and dispersal dynamics is vital for successful management. Our study used a 360 base-pair mitochondrial control region locus sequenced for 103 individuals and 18 nuclear microsatellite loci genotyped for 245 individuals to investigate population structure in the Atlantic and Pacific populations of the pelagic seabird, Leach’s storm-petrel Oceanodroma leucorhoa leucorhoa. This species is under intense predation pressure at one regionally important colony on St Kilda, Scotland, where a disparity between population decline and predation rates hints at immigration from other large colonies. AMOVA, FST, ΦST and Bayesian cluster analyses revealed no genetic structure among Atlantic colonies (Global ΦST = -0.02 P >0.05, Global FST = 0.003, P>0.05, STRUCTURE K = 1), consistent with either contemporary gene flow or strong historical association within the ocean basin. The Pacific and Atlantic populations are genetically distinct (Global ΦST = 0.32 P <0.0001, Global FST = 0.04, P <0.0001, STRUCTURE K = 2), but evidence for inter-ocean exchange was found with individual exclusion/assignment and population coalescent analyses. These findings highlight the importance of conserving multiple colonies at a number of different sites and suggest that management of this seabird may be best viewed at an oceanic scale. Moreover, our study provides an illustration of how long-distance movement may ameliorate the potentially deleterious impacts of localised environmental change, although direct measures of dispersal are still required to better understand this process.