A theoretical study is conducted to examine the effects of oxygen enrichment of intake air and exhaust gas recirculation (EGR) on heavy-duty (HD) diesel engine performance characteristics and pollutant emissions. A phenomenological multi-zone model was properly modified and used to assess the impact of intake air oxygen-enhancement and EGR on the operating and environmental behavior of a HD diesel engine under various operating conditions. Initially, an experimental validation was performed to assess the predictive ability of the multi-zone model using existing data from a HD turbocharged common-rail diesel engine at the 12 operating points of the European Stationary Cycle (ESC) considering certain high-pressure cooled EGR rate at each operating point. A theoretical investigation was conducted for diesel operation without EGR considering a variation of intake air oxygen fraction from 21% to 25%v/v under the following two operating modes: (1) Constant fuelling rate and (2) Increased fuelling rate to sustain constant in-cylinder average air/fuel equivalence ratio (lambda). The predictions of this analysis showed a considerable reduction of exhaust soot and small improvement of brake specific fuel consumption (BSFC). However, in both modes of oxygen-enhanced diesel operation. a significant increase of NO emissions was observed, which created the motivation to examine the implementation of EGR. Hence, a second theoretical investigation was performed considering variation of high-pressure cooled EGR from 0% to 30%v/v for the aforementioned intake air oxygen mole fractions under two different modes of engine operation: (1) Constant inlet pressure and (2) Increased inlet pressure to sustain constant average air/fuel equivalence ratio (lambda). The theoretical results of this combined analysis showed a considerable reduction of soot and NO emissions accompanied by limited or imperceptible penalties in BSFC, which are more pronounced in the case of constant lambda due to increase of brake power output. Consequently, there is a promising path for simultaneous reduction of soot and NO emissions from heavy-duty diesel engines without serious detrimental effects on specific fuel consumption by combining intake air oxygen-enrichment and cooled EGR.