Former industrially contaminated sites are a burden from the past that still pose environmental risks. During the second half of the 20th century, the Pavlodar region in North Kazakhstan had been a part of Soviet Union’s industrial system that operated a chlor-alkali plant (CAP). The former CAP discharged approximately 135 t Hg into nearby Lake Balkyldak with total losses to water, soil, and air estimated around 1000 t. Pollution by potentially toxic elements (PTEs) due to former and currently active industrial enterprises is an under-investigated concern in the Pavlodar region. The present study aims to provide a much-needed update on the situation around the CAP area by evaluating the contamination by Hg and other selected PTEs (As, Ba, Cd, Co, Cr, Cu, Mn, Ni, Pb, Sb, Se, Zn) on the surrounding environment of the CAP and in the nearby urban zone. Soil, sediment, surface water, and groundwater samples have been collected in several sampling campaigns carried out in 2018 and 2019. Several samples had Hg concentrations exceeding maximum permissible concentrations (MPC), for soils and sediments (in mg/kg; range: 0.0006 to 24, average: 0.56) and for surface water and groundwater (in µg/L; range: 0.004 to 1340, average: 93). Critically high concentrations were mostly measured in the vicinity of Lake Balkyldak, where the majority of Hg had been discharged by the former CAP, indicating persisting Hg pollution in the studied zone. A comparison of the PTEs concentrations in soil and sediments showed less severe pollution but still some elevated values for As, Ba, Co, Cu, Mn, Ni, and Se. The inter-elemental relationship between Hg and assessed PTEs was weak, indicating the presence of sources independent from Hg emitting sources. Further research on Hg contamination on the exact territory of the former CAP is needed, and a detailed human health risk characterization to identify potential unacceptable risks is strongly recommended.