The factors underlying gene flow and genomic population structure in vagile seabirds arenotoriously difficult to understand due to their complex ecology with diverse dispersal barriers and extensive periods at sea. Yet, such understanding is vital for conservation management of seabirds that are globally declining at alarming rates. Here, we elucidate thepopulation structure of the Atlantic puffin (Fratercula arctica) by assembling its referencegenome and analyzing genome-wide resequencing data of 72 individuals from 12 colonies.We identify four large, genetically distinct clusters, observe isolation-by-distance betweencolonies within these clusters, and obtain evidence for a secondary contact zone. Theseobservations disagree with the current taxonomy, and show that a complex set of contemporary biotic factors impede gene flow over different spatial scales. Our results highlightthe power of whole genome data to reveal unexpected population structure in vagile marineseabirds and its value for seabird taxonomy, evolution and conservation