Formaldehyde (HCHO) is a common volatile organic compound (VOC) in indoor environments, causing significant health hazards and even leading to serious diseases. Therefore, real-time monitoring HCHO is essential. The Co3O4-based chemiresistive gas sensors are promising candidates for monitoring HCHO. However, it is challenging to construct Co3O4-based HCHO sensors with fast response property. In this work, a surface reconstruction strategy was proposed to prepare novel Co3O4-based sensing materials. First, trace N, C co-doped Co3O4 (NC-Co3O4) was synthesized by pyrolysis of ZIF-67 in Ar atmosphere at 700 ∘ C. Then, the surface of NC-Co3O4 was subsequently reconstructed by H2SO4 etching, leading to forming the stable surfaces with low concentration of oxygen vacancy and Co ions (NC-Co3O4-E80). The gas sensing experiments demonstrate that the optimal NC-Co3O4-E80 exhibits enhanced performance to HCHO detection, including the response value of 103.8% (42.1% for NC-Co3O4) to 100 ppm HCHO at 140 ∘ C, short response time of 3 s (62 s for NC-Co3O4), short recovery time of 10 s (53 s for NC-Co3O4), and excellent cycle repeatability. This trait can play a significant role in fabricating HCHO sensors for real-time detection.