Heavy metal contamination in freshwater systems poses critical risks to aquatic organisms, particularly through bioaccumulation and sublethal cellular damage. This study evaluates the use of genotoxic and histopathological biomarkers—specifically micronucleus (MN) formation in erythrocytes and gill tissue alterations—in wild Cyprinidae as indicators of heavy metal pollution along the Brantas River, Malang, Indonesia. Fish were sampled from three sites representing an upstream-to-downstream gradient: Batu (Site A), Dinoyo (Site B), and Kepanjen (Site C). Gill tissues from 180 individuals were analyzed for lead (Pb), cadmium (Cd), mercury (Hg), copper (Cu), and zinc (Zn) concentrations using atomic absorption spectrophotometry. Genotoxicity was assessed through MN assays on peripheral blood erythrocytes, while gill histopathological changes were evaluated and quantified using a Gill Histopathological Index (GHI). Results demonstrated a clear spatial increase in metal accumulation, with Pb levels rising from 0.85 ± 0.22 mg/kg at Site A to 4.87 ± 0.61 mg/kg at Site C. Correspondingly, MN frequency increased from 1.34 ± 0.41‰ to 6.92 ± 0.88‰, and GHI scores rose from 3.2 ± 0.9 to 11.4 ± 2.2. The increases in micronucleus frequency (p < 0.001), gill histopathology scores (p < 0.001), and heavy metal concentrations (p < 0.01 to p < 0.001) across sites were statistically significant, confirming a strong correlation between pollution level and biological responses. Significant correlations were observed between heavy metal concentrations and both MN frequency and gill pathology severity. These findings validate the combined use of MN assay and gill histopathology as sensitive, complementary biomarkers for monitoring heavy metal pollution in riverine ecosystems. The study underscores the need for integrated biomonitoring strategies and strengthened pollution management in tropical freshwater systems.