Recent 2010 emissions standards for heavy-duty engines have established a limit of oxides of nitrogen (NOx) emissions of 0.20 g/bhp-hr; however, it is projected that even when the entire on-road fleet of heavy-duty vehicles operating in California is compliant with 2010 emission standards, the National Ambient Air Quality Standards (NAAQS) requirement for ambient particulate matter and Ozone will not be achieved without further reduction in NOx emissions. The California Air Resources Board (ARB) funded a research program to explore the feasibility of achieving 0.02 g/bhp-hr NOx emissions. This paper details the work executed to achieve 0.02 g/bhp-hr NOx emissions over the heavy-duty Federal Test Procedure (FTP) with a heavy-duty natural gas engine equipped with a three-way catalyst. A Cummins ISX-12G natural gas engine was modified and coupled to an advanced catalyst system. In addition to close-coupled and underfloor catalysts, a high energy ignition system and advanced EGR-fuel-air mixer were incorporated into the engine system. New cold start calibrations were developed, improved air-fuel ratio control was implemented, and the engine was able to demonstrate composite NOx emissions of 0.015 g/bhp-hr for the FTP, and 0.008 g/bhp-hr for the World Harmonized Transient Cycle (WHTC). Additional calibration may yield further improvements for duty cycles beyond the FTP and WHTC. Results from this study demonstrate a potential pathway to achieving ultra-low NOx emissions on future heavy-duty vehicles.