Understanding the health risks of toxic elements (TEs) in urban park soils and determining their priority control factors are crucial for public health and pollution management. Soil samples were collected from 33 urban parks in Guiyang, a typical karstic city. For each park, 15–45 topsoil samples were collected according to the area and then thoroughly mixed to obtain a representative sample. The results showed that the mean concentrations of TEs in park soils (22.5, 0.37, 88.6, 43.7, 0.26, 39.9, 44.7, and 101.0 mg/kg for As, Cd, Cr, Cu, Hg, Ni, Pb, and Zn, respectively) were higher than their background values. Approximately 54.5% and 33.3% of enrichment factor (EF) values reached moderately enriched to significantly enriched levels for Cd and Hg, respectively. Moreover, 54.5% and 42.4% of monomial potential ecological index (EI) values were at considerable to high risk levels for Cd and Hg, respectively. These results illustrate that Cd and Hg pose high ecological risks. According to the potential ecological risk index (RI) values, 21.2% of the parks were exposed to considerable ecological risk and 48.5% were at moderate risk. Based on the positive matrix factorization (PMF) model, four sources governing TE contamination (including coal combustion, natural sources, traffic emissions, and industrial activities) were identified, with contribution rates of 32.3%, 31.0%, 19.6%, and 17.1%, respectively. A probabilistic health risk assessment showed acceptable non-carcinogenic risks and high levels of carcinogenic risk in all populations. Based on the source-specific health risk assessment, arsenic from coal combustion was determined to be a major contributor to human health risks. Although several efforts have been made by the local government to eliminate coal-borne arsenicosis, our results revealed that the accumulation of arsenic in the soil due to coal combustion poses a potential threat to human health.