Sixty-seven surface marine sediment samples in the <63 μm fraction collected from the coast of Sfax (Tunisia) were analyzed by inductively coupled plasma-atomic emission spectrometry for seven heavy metals (Pb, Ni, Cu, Cr, Zn, Cd, and Fe). Metal concentrations were compared with natural values, marine sediment quality standards, and also with other results concerning sediments from several Mediterranean coasts. The study of their spatial distributions refined by complementary approaches including principal component analysis, enrichment factors, and geoaccumulation index showed a significant impact of multiple anthropogenic sources. These included industrial sources and municipal discharges of the urban Sfax and also non-controlled discharges in rural zones close to the coastline. Moderate pollution of sediments, especially by Pb, Zn, and Ni, was shown to exist in localized sites. Besides, it was shown that other sites, slightly to highly enriched in terms of Cu, Cr, and Cd, are characterized by a quality of sediments varying from unpolluted to moderately polluted.