Airfoil fin printed circuit heat exchangers (PCHEs) have broad application prospects in the naval, aerospace, electric power, and petrochemical industries. The channel structure is a critical factor affecting their thermal-hydraulic characteristics. In this study, a novel PCHE channel structure with staggered NACA 0025 airfoil-shaped fins was proposed; accordingly, the thermal-hydraulic characteristics of the novel channel structure using carbon dioxide as the working fluid at different fin heights under different operating conditions (trans-, near-, and far-critical) were investigated. The results indicated that the thermal-hydraulic performance of the PCHE under the trans-critical operating condition was better than that under the near-critical and far-critical operating conditions. Compared with conventional airfoil fin channels, the novel airfoil fin channel attained comparable comprehensive performance while reducing the fin volume by 50%, thus achieving a more lightweight PCHE design. The comprehensive performance of the PCHE was the poorest when the fin height was slightly below the channel height, which should be avoided during the design of airfoil fin PCHEs. The results provide theoretical support for the design and optimization of airfoil fin PCHEs.