Arsenic and lead released from coal-fired power plant have caused great damage to environment and human health, making it critical to remove arsenic and lead simultaneously. The adsorption characteristics of HTMs (As2O3, Pb0, PbO and PbCl2) on the surface of single atom iron adsorbents supported with graphene-based substrates (Fe/GS) were systematically investigated through density functional theory calculation. The magnetic properties, bonding mechanism, reaction temperature and competitive adsorption behaviors were all considered in this work. Results demonstrated that Fe/GS of single vacancy with three nitrogen atoms doping (Fe/SV-N3) shows the most excellent adsorption capacity for HTMs among four types of Fe/GS. The adsorption of HTMs on Fe/SV-N3 belongs to stable chemisorption, and the adsorption can take place spontaneously when the temperature is below 700 K. To compare with the previously studied Hg0 system, the competitive adsorption behaviors of Hg0 and HTMs on Fe/SV-N3 were studied through relative adsorption ratio, Fe/SV-N3 will preferentially adsorb Pb0 and PbO when Hg0 and HTMs occur simultaneously at the temperature range of 300–1000 K. Therefore, Fe/SV-N3 is suggested to be a potential new material for gas detection and simultaneous removal of pollutants from coal-fired power plants.