Surface sediment samples from Strymonikos and Ierissos Gulfs were analyzed for Cu, Pb, Zn, Cr and Ni. The results showed that the sediment of Ierissos Gulf is more polluted with Cu, Pb, and Zn as compared to that of Strymonikos Gulf. The benthal area located off the load-out facility of the mining operations in the town of Stratoni, in Ierissos Gulf is established as the most polluted region. The distribution of Cr and Ni in both gulfs indicates the natural origin of these metals with the weathering of Strymon River and of other smaller rivers rocks being responsible for their enrichment.