This paper provides the first critical synopsis of contamination by selected trace elements in the whole Danube Delta (Romania/Ukraine) to: identify general patterns of contamination by trace elements across the Delta, provide recommendations to refine existing monitoring networks and discuss the potential toxicity of trace elements in the whole Delta. Sediment samples were collected between 2004 and 2007 in the three main branches of the Delta (Chilia, Sulina and Sfantu Gheorghe) and in the secondary delta of the Chilia branch. Samples were analyzed for trace elements (Cd, Co, Cr, Cu, Ni, Pb, V, and Zn) and TiO2, Fe2O3, MnO, CaCO3 and total organic carbon. Cluster analysis (CA) and Principal Component Analysis (PCA) showed that levels of Cd, Cu, Pb, and Zn were influenced by anthropogenic activities. At the opposite, concentrations of Cr and Ni largely originated from the weathering of rocks located in the Romanian part of the Danube catchment and naturally rich in these elements. Data analysis using Self-Organizing Maps confirmed the conclusions of CA/PCA and further detected that the contamination tended to be higher in the Chilia and Sulina arms than in the Sfantu Gheorghe arm. The potential ecological risks due to trace element contamination in the Danube Delta could be identified as moderate and localized, provided that the presence of the natural sources of Cr and Ni was properly considered. The available results suggest that monitoring sediment quality at the mouths of Sulina and Sfantu Gheorghe arms is probably enough to get a picture of the sediment quality along their entire lengths. However, a larger network of monitoring points is necessary in the Chilia and secondary Chilia delta to account for the presence of local point sources and for the more complex hydrodynamic of this part of the Danube Delta.