Chemically modifying graphene (such as chemical doping) is a commonly used method to improve its formaldehyde sensing properties, but the microscopic mechanisms of heteroatoms in the adsorption and sensing process are still unclear. In this paper, the adsorption and sensing properties of formaldehyde on graphene surfaces modified by X doping (X = B, N, O, P, S, Mg and Al) were systematically investigated by first-principles calculations. The adsorption geometries, adsorption energies, charge transfers, and electronic structures were obtained and analyzed. The adsorption strengths of HCHO molecule on the Mg- and Al-doped graphene surfaces were stronger than those of non-metal (B, N, O, P and S)-doped cases. These results showed that the Mg- or Al-doped graphene was better for HCHO detecting than the non-metal-doped graphene systems. The sensing properties were simulated by theNEGF method for the two-probe nano-sensors constructed from Al- and Mg-doped graphene. The maximum sensing responses of nano-sensors based on Al- and Mg-doped graphene were obtained to be 107% and 60%, respectively. The present study supplies a theoretical basis for designing superior graphene-based HCHO gas sensors.