Efficient reef management strategies rely on detailed knowledge of biological exchange dynamics. At present, available connectivity information on Mexican Atlantic reefs is scarce, particularly concerning the Veracruz Reef System (VRS), which is located in the south-western Gulf of Mexico. This study used a hierarchically nested sampling design to evaluate the levels of genetic connectivity both within and between the Mexican Caribbean (MC) and VRS reef regions; all of the studied reefs are marine protected areas. Microsatellites were used as genetic markers, and bicolor damselfish (Stegastes partitus) recruits were used as a biological model. The paired genetic differentiation index between regions (Fst (ENA) = 0.008) was lower than the global index (Fst (ENA) = 0.027), suggesting that the stronger restrictions to gene flow may be located inside the regions rather than between them. The AMOVA results supported this explanation, as the differences were only non-significant between regions. In the VRS, Santiaguillo reef was associated with low genetic connectivity levels, whilst within the MC region the group formed by Chinchorro Bank and Cozumel exhibited a restriction to gene flow with Puerto Morelos, their northernmost reef. Despite their spatial separation, reefs from different regions (Puerto Morelos and Anegada de Adentro) showed the lowest, albeit significant, genetic difference, meaning that a subtle genetic connectivity exists at the regional scale. The detected composite flow pattern is likely related to self-recruitment and cohesive dispersal processes interacting with current patterns, which may favour genetic connections under specific conditions. The results presented here suggest that coral reef management in the Mexican Atlantic Ocean should consider large scale measures in addition to appropriate local actions to protect reef fish populations.