Research indicated that more than 60% of the potential energy from the fuel input in the internal combustion engine (ICE) is lost as heat in exhaust gases and engine coolant systems. Therefore, utilizing heat from these wasted energy sources has attracted special attention from scientists because this is a quite simple but highly effective solution to improve the engine’s thermal efficiency. This study will focus on calculating, designing, and evaluating the waste heat recovery potential of an Exhaust Air Heat Exchanger (EAHE) used in vehicle air heating systems. Two structure tubes are adopted to enhance the heat transfer capabilities of the EAHE. The flow and heat transfer characteristics of these tubes are comprehensively investigated and compared using computational fluid dynamics (CFD). The research results show that the efficiency of the heat exchanger depends not only on the temperature and speed of the flow of air and exhaust gases moving through the device but also on the tube structure, which is one of the important parameters. Especially when the heat exchanger uses a wavy tube structure, the heat recovery efficiency of the exhaust gases can reach approximately 20.29%.