A previously derived 12-step, 16-species augmented reduced mechanism (ARM), based on GRI-Mech 1.2, was shown to be comprehensive for methane oxidation at the levels of global response as well as detailed flame structure. The present study updates and extends this effort by basing the reduction an the recently released GRI-Mech 3.0 and by including the description of NOx formation. Specifically, by assuming all the nitrogen-containing species (except N-2) are in steady state, an equivalent 12-step ARM was developed. Subsequently, a 14-step and a 15-step ARMs were derived to account for NO formation. The 14-step ARM is basically the 12-step ARM plus two more steps that respectively describe the thermal, prompt, and nitrous oxide mechanisms, and the prompt mechanism Further inclusion of NH3-related reactions yielded the 15-step ARM. A 17-step ARM was also developed to account for the additional emissions of nitrogen dioxide and nitrous oxide. It is shown that, by including such optimum numbers of non-steady-state intermediates for the various mechanisms the present ARMs exhibit good to excellent performance in predicting a wide range of combustion phenomena under extensive thermodynamic parametric variations.