Heavy metal accumulation in coastal sediments has become a major environmental concern due to increasing anthropogenic activities. The southern western Johor waters include Sungai Pulai and the western Johor Strait. Sungai Pulai contains the largest mangrove ecosystem in Johor, Malaysia and is designated as a Ramsar site. It discharges into the western Johor Strait, a coastal environment influenced by industrial, port, shipping, and aquaculture activities. This study aimed to determine the total concentrations and spatial distributions of selected heavy metals in the surficial sediments of Sungai Pulai and the western Johor Strait, evaluate the relationships between sediment grain size and heavy metal concentrations, and assess sediment pollution status. A total of 35 surficial sediment samples were collected from 21 stations in Sungai Pulai and 14 stations in the western Johor Strait. Concentrations of Cu, Zn, Cd, Pb, As, and Hg were determined using Inductively Coupled Plasma Mass Spectrometry (ICP-MS). Sediment grain size was analysed using dry sieving and laser diffraction, while Pearson correlation analysis was performed to examine the relationships between sediment characteristics and heavy metal concentrations. Contamination levels were evaluated using the contamination factor (CF), pollution load index (PLI), and geo-accumulation index (Igeo). Sungai Pulai exhibited higher and more variable heavy metal concentrations than the western Johor Strait, particularly for Zn, As, and Pb, indicating localized enrichment and potential contamination hotspots. Although concentrations were generally lower in the western Johor Strait, elevated As concentrations were observed at stations JHR-10 to JHR-14 near the Sungai Pulai river mouth, suggesting the influence of upstream inputs and nearby port activities. Significant positive correlations (p < 0.01) among most heavy metals indicate common anthropogenic sources associated with industrial, maritime, and aquaculture activities, while sediment grain size was identified as an important factor controlling heavy metal distribution. Elevated Igeo values (grade 5) for As and PLI values greater than 1 at most Sungai Pulai stations indicate moderate to significant contamination, whereas only two stations (JHR-2 and JHR-3) in the western Johor Strait exceeded the PLI threshold. Overall, the surficial sediments of Sungai Pulai were more contaminated than those of the western Johor Strait, although localized pollution hotspots were identified near the river mouth and in the eastern part of the western Johor Strait. These findings provide valuable baseline information for environmental monitoring and support sustainable management of this ecologically important coastal ecosystem.