Bluefish (Pomatomus saltatrix), a highly migratory cosmopolitan predator, is the only extant representative of the family Pomatomidae. It has been the subject of many studies due to its commercial and recreational value, but much less research has been conducted on its global population structure. Here we investigate the population structure of this species and the effects of present and past oceanographic barriers to dispersal in its North Atlantic, Mediterranean, Marmara, and Black sea populations. We employed mitochondrial (cytochrome b and cytochrome oxidase subunit I genes) and nuclear (eight microsatellite loci) DNA as molecular markers. Three main genetic units of Bluefish were identified: American (West Atlantic waters), Spanish (East Atlantic–Western Mediterranean regions), and Turkish (Eastern Mediterranean, Marmara, and Black seas). Our results suggested that Bluefish is panmictic in the northwest Atlantic Ocean but not in the Mediterranean Sea. The common ancestor of the studied populations was traced back to the interglacial cycle Aftonian II, and the separation between clades was estimated to have occurred during glacial periods, likely due to migrations to refuges and the closure of the Mediterranean Sea. In conclusion, paleoclimate seems to have been fundamental for shaping the present genetic lineages of Pomatomus saltatrix.