Highly sensitive and selective gas sensors based on heterostructured p-CuO/n-SnO₂ core-shell nanowires (NWs) with precisely controlled shell thickness were synthesized through a sequential process combining a solution processing and atomic layer deposition. The gas sensing devices were fabricated on micro-electromechanical systems, which has triggered great research interest for low power consumption and highly integrated design. The designed p-CuO/n-SnO₂ core-shell NW structured gas sensors exhibited superior gas sensing performance, which is closely related to the thickness of the SnO₂ shell. Specifically, p-CuO/n-SnO₂ core-shell NWs with a 24 nm thick SnO₂ shell displayed a high sensitivity (R_a/R_g) of 2.42, whose rate of resistance change (i.e. 1.42) is 3 times higher than the pristine CuO NW sensor when detecting 50 ppm formaldehyde (HCHO) at 250 °C. The enhanced gas sensing performance could be attributed to the formation of p-n heterojunction which was revealed by specific band alignment and the heterojunction-depletion model. Besides, the well-structured p-CuO/n-SnO₂ core-shell NWs achieved excellent selectivity for HCHO from commonly occurred reducing gases. In a word, such heterostructured p-CuO/n-SnO₂ core-shell NW gas sensors demonstrate a feasible approach for enhanced sensitive and selective HCHO detection.