A 15-step, 19-species reduced mechanism for methane oxidation was derived from GRI-Mech 3.0 using the method of directed relation graph (DRG) and quasi steady state (QSS) assumptions. The concentrations of the QSS species were solved analytically for maximum efficiency. The reduced mechanism was validated with a variety of phenomena including perfectly stirred reactors, autoignition, and premixed and non-premixed flames, with less than 10% accuracy loss observed over a wide range of parameters for both global system parameters and species profiles. Compared with the 12-step and 16-species augmented reduced mechanism (ARM) previously developed by Sung, Law & Chen, three species, namely O, CH3OH, and CH2CO were removed from the QSS species list. The effects of these three species on the accuracy of global system parameters and species concentrations, as well as the convergence rate of the algebraic iterations for solving QSS species concentrations, were discussed. The present reduced mechanisms were found to be more efficient to apply for both homogenous and diffusive systems, because of three factors: the inclusion of a skeletal reduction state, improved selection of QSS species, and analytic solution of the QSS species concentrations. This mechanism was then augmented with the reactions involving NO formation, and validated in both homogeneous and diffusive systems.