The coastal marine environment of the Northwest Atlantic contains strong environmental gradients that create distinct marine biogeographic provinces by limiting dispersal, recruitment, and survival. This region has also been subjected to numerous Pleistocene glacial cycles, resulting in repeated extirpations and recolonizations in northern populations of marine organisms. In this study, we examined patterns of genetic structure and historical demography in the Atlantic silverside, Menidia menidia, an annual marine fish with high dispersal potential but with well-documented patterns of clinal phenotypic adaptation along the environmental gradients of the Northwest Atlantic. Contrary to previous studies indicating genetic homogeneity that should preclude regional adaptation, results demonstrate subtle but significant (F_ST = 0.07; P < 0.0001) genetic structure among three phylogeographic regions that partially correspond with biogeographic provinces, suggesting regional limits to gene flow. Tests for non-equilibrium population dynamics and latitudinal patterns in genetic diversity indicate northward population expansion from a single southern refugium following the last glacial maximum, suggesting that phylogeographic and phenotypic patterns have relatively recent origins. The recovery of phylogeographic structure and the partial correspondence of these regions to recognized biogeographic provinces suggest that the environmental gradients that shape biogeographic patterns in the Northwest Atlantic may also limit gene flow in M. menidia, creating phylogeographic structure and contributing to the creation of latitudinal phenotypic clines in this species.