A novel heat exchanger unit structure was adopted to improve the thermal-hydraulic performance of compressed humid air and high-temperature flue-gas in a megawatt (MW) grade humid air turbine (HAT) cycle. Staggered airfoil fin channels and rectangular straight fin channels were projected for the compressed humid air and flue-gas, respectively. A three-dimensional model of the heat exchanger unit structure was built to simulate the heat transfer and flow of flue-gas and compressed humid air under different moisture content, mass flow-rate, and inlet temperature of humid air. The thermal-hydraulic performances of staggered airfoil channels were contrasted with that of straight and zigzag channels. The results showed that the airfoil channel has the best comprehensive thermal-hydraulic performance. Heat transfer and friction factor correlations were proposed to predict thermal-hydraulic performances of the compressed humid air flowing in the airfoil channel. The effects of moisture content on the heat transfer and flow characteristics were quantitatively described using correlations. The moisture content of the humid air is the main influence factor on heat transfer performance. In present study, the results and correlations can provide guidance for the design and application of recuperator structures with airfoil fins for the MW grade HAT cycle.