The spatial distribution and geoaccumulation indices of four heavy metals were investigated in very shallow marine sediments of southwestern Spain. Surface sediments were collected from 43 sites with water depth ranging from 3 to 20 m. High to very high pollution levels (I geo > 4 for zinc, lead and copper) were detected near the end of the Huelva bank, whereas chromium shows a more hazardous distribution in the southwestern Spanish littoral. Low to moderate heavy metal contents (mainly zinc and lead) were also observed in other two areas at different water depths (Isla Cristina-Piedras River: 10–18 m water depth; Mazagón–Matalascañas: <10 m water depth), whereas unpolluted to moderately polluted sediments were detected in the very shallow zones (<8 m water depth) located between the mouths of the Guadiana and the Piedras Rivers. A regional scenario indicates a strong pollution of the adjacent marine areas by polluted inputs derived from the Tinto–Odiel rivers, with a partial transport of heavy metals by W–E littoral currents even 40 km eastward. The Guadiana River is an additional source of zinc–lead contamination near the Spanish–Portuguese border, mainly at water depths up to 10 m. All these rivers are affected by acid mine drainage processes, derived from millennial mining activities. This pollution affects the sediment quality even 40 km eastward.