Marine sediment pollution plays a key role in the global health of the seas. This research focuses on the evaluation of the concentration and distribution of heavy metals in the Mediterranean Sea. Data from different coastal locations in the southeast of Mallorca have been compared and traces of heavy metals have been identified in more than 200 samples. The magnitude of the accumulation of heavy metals shows the following trend: high presence of Hg > Ni > Cu; moderate for As > Pb and low for the rest of heavy metals. Sediment quality guides (NOAA and EPA) have been used as well as a Regional Index with background values. The spatial distribution pattern of heavy metals shows a general decreasing trend from the littoral coast near wastewater discharges towards the open sea. This distribution pattern in the Balearic Mediterranean Sea shows possible similar sources of pollution related to anthropogenic activities and large volumes of poorly treated wastewater discharges. The study shows how the distribution patterns of heavy metals in marine sediments is related to a decrease in Posedonia. It is crucial to comply with the current legislation of the European Union regarding the sustainability of the maritime seacoast and the protection of very fragile ecosystems such as Posidonia oceanica. In addition, the data are a good tool for designing management strategies in coastal areas.