Granulometry, mineralogy, and trace element concentrations are determined in marine sediments from thirty-six sampling sites in the littoral environment of the Gulf of Milazzo (NE Sicily). Sediment samples were collected in August 2008, along 18 seaward transects, at water depths of −10, −20 and −30 m, by using a Van Veen grab. Grain-size analysis shows predominance of sand (56%) and silt (35%) fractions with respect to clay (7%) and gravel (2%) fractions. Bulk mineralogical analysis documents the presence of quartz, micas, feldspars, calcite, and chlorite, which reflect erosion processes affecting the Kabilian-Calabrian Units. Concentrations of most trace elements in the deeper sediments were notably higher than shallower ones, due to the gradual increase of the fine fraction (<63 μm). Concentrations of Cr, Ni, Pb and, at lesser extent, Zn and Cu in the <63 μm fraction appear to be potentially hazardous, exceeding national and international regulatory guidelines, both close to the Milazzo industrial area and at Capo Rasocolmo. Trace element mean values from the Gulf of Milazzo are comparable with those measured in polluted sediments collected in the Gulf of Palermo and Augusta Bay with a moderate enrichment in Zn. Different sources of trace elements and different geochemical mechanisms are probably responsible of this distribution. Among these sources and mechanisms, local anthropogenic inputs, different contents of organic matter, and surface water circulation may be invoked.