In order to document the distribution of organic-walled dinoflagellate cysts (dinocysts) and their relationship with sea-surface parameters (temperature, salinity, primary productivity), palynological analyses were performed on 44 surface sediment samples from the Gulf of Mexico (17°N to 29°N). Samples display low to moderate concentrations with values ranging from 78 to 3576 dinocysts·g− 1 dry weight sediment. Assemblages are dominated by either Brigantedinium spp. or Polysphaeridium zoharyi along with the phototrophic taxa Spiniferites spp. and Operculodinium spp. Redundancy analyses (RDA) identified the distance to the coast and/or water depth and annual temperature as being the most important factors that control cyst distribution in the Gulf of Mexico. The first two axes explain respectively 44.7% and 20% of the total variance. The inshore to offshore trend in cyst distribution emphasized by the RDA involves changes in associations of species with the presence of Impagidinium spp. in more oceanic assemblages and higher representation of P. zoharyi nearshore. This latter species, produced by the potentially toxic dinoflagellate Pyrodinium bahamense, reaches very high abundances notably on the west Florida shelf and in the Mexican lagoons. Additionally, Melitasphaeridium choanophorum, which was considered to have gone extinct by the end of the Pleistocene, appears as a modern component of marine sediment from the north and southwestern Gulf. Our results thus demonstrate a biostratigraphical range extending to the present, at least in the study area. This palynological investigation highlights the importance of the Gulf of Mexico as potential refuge for late Cenozoic species thought to be extinct.