Heavy metal(loid)s are frequently detected in vegetables posing potential human health risks, especially for those grown around mining areas. However, the oral bioaccessibility and gingival cytotoxicity of heavy metals in wild vegetables remain unclear. In this study, we assessed the total and bioaccessible Cr, As, Cd, Pb, and Ni in four wild vegetables from mining areas in Southwest China. In addition, the cytotoxicity and underlying mechanisms of vegetable saliva extracts on human gingival epithelial cells (HGEC) were studied. The Plantago asiatica L. (PAL) showed the highest bioaccessible Cr, As, Cd, and Pb, while the greatest bioaccessible Ni was in Taraxacum mongolicum (TMM). The Pteridium aquilinum (PAM), Chenopodium album L. (CAL), and TMM extracts decreased cell viability, induced apoptosis, caused DNA damage, and disrupted associated gene expressions. However, PAL extracts which have the highest bioaccessible heavy metals did not present adverse effects on HGEC, which may be due to its inhibition of apoptosis by upregulating p53 and Bcl-2. Our results indicated that polluted vegetable intake caused toxic effects on human gingiva. The heavy metals in vegetables were not positively related to human health risks. Collectively, both bioaccessibility and toxic data should be considered for accurate risk assessment.