The aim of this study was to analyze 16 trace elements (Al, As, B, Ba, Cd, Co, Cr, Cu, Fe, Li, Mn, Mo, Ni, Pb, Sr, and Zn) in different barbel (Barbus barbus) tissues and to detect the presence of genotoxic effects in erythrocytes with the alkaline comet assay. Barbel specimens were collected in the Danube river near Belgrade, Serbia, where the discharge of untreated communal and industrial wastewaters is likely to produce negative effects on fish residing in this area. The highest concentrations of Sr, Mn, Fe, Ba, B, and Al were found in gills, Mo and Cu in liver, and As and Zn in gonads. Concentrations of Zn and Fe were above maximum acceptable concentrations (MACs) in a number of gonad, gill, and liver samples. Three-year-old barbel specimens had higher tail moment and Zn concentrations in gills (1.71 and 51.20 μg/g dw, resp.) than 5-year-old specimens (0.85 and 42.51 μg/g dw, resp.). Results indicate that the younger barbel specimens might be more suitable for the monitoring of environmental pollution.