Recently conducted work has been funded by the California Air Resources Board (CARB) to explore the feasibility of achieving 0.02 g/bhp-hr NOX emissions for heavy-duty on-road engines. In addition to NOX emissions, greenhouse gas (GHG), CO2 and methane emissions regulations from heavy-duty engines are also becoming more stringent. To achieve low cold-start NOX and methane emissions, the exhaust aftertreatment must be brought up to temperature quickly while keeping proper air-fuel ratio control; however, a balance between catalyst light-off and fuel penalty must be addressed to meet future CO2 emissions regulations. This paper details the work executed to improve catalyst light-off for a natural gas engine with a close-coupled and an underfloor three-way-catalyst while meeting an FTP NOX emission target of 0.02 g/bhp-hr and minimizing any fuel penalty. Two methods for achieving fast catalyst light-off were examined: 1) secondary air injection upstream of the front face of the close-coupled catalyst, and 2) operating half of the cylinders rich and the other half of the cylinders lean. Results from this study demonstrate a potential pathway to achieving ultra-low NOX emissions and future GHG Phase 2 standards on heavy-duty vehicles.