The world's largest cities are characterized by environmental pollution, which endangers human health and biological species. Therefore, environmental monitoring and mapping of pollution levels are important tasks. To this end, we applied regression kriging (RK) and random forest (RF) for digital mapping of potentially toxic elements (PTEs) on the territory of Saint Petersburg (Russia). We predicted concentrations of As, Cd, Cu, Hg, Ni, Pb and Zn PTEs based on 87 sites. The covariates were represented by remote sensing, terrain and anthropogenic variables. The results showed that the elements were characterized by high variability and their content varied between 1 and 37 mg/kg for As, 0.1 and 2.7 for Cd, 4.7 and 674 for Cu, 0.005 and 3.6 for Hg, 2.8 and 66.8 for Ni, 3.4 and 858.8 for Pb, 15.4 and 1306.5 for Zn. We found that RK was the best performing model for Cu, Hg, Ni, Pb and Zn, with the lowest mean absolute error (MAE), root mean squared error (RMSE), and highest coefficient of determination (R2) and Nash–Sutcliffe model efficiency coefficient (NSE) values. RF method was better for predicting As content, while the performance of the models for Cd was the same. Nevertheless, R2 values remained below 0.23, signifying a difficulty in effectively modeling PTEs within urbanized regions. The study provides insight into the benefits of combining regression analysis and kriging, and highlights the importance of considering multiple modeling approaches in spatial prediction of PTEs.