Heat recovery from exhaust gas streams is applicable to a wide variety of industries. Two problems encountered in exhaust gas heat recovery are: the high heat transfer resistance of gases and the presence of entrained particulate matter, which can limit the use of extended surface area. Standard heat exchangers use round tube. This study uses Computational Fluid Dynamics (CFD) to investigate whether round or another shape is the best tube selection for exhaust heat recovery. Tube shape rankings are based on taking into account heat transfer, gas flow resistance and foulability. Foulability is inferred from the average wall shear stress around the front or back of each shape. An estimated asymptotic fouling resistance is used to calculate an equivalent fouled j factor, jf. CFD results suggest the best tube for exhaust heat recovery is an elliptical tube. The ellipse shape produced j/f and jf/f ratios (where f is the tube bank friction factor) over 1.5 times larger than that of standard round tube. A flattened round tube is also promising and may be the practical and economic optimum.