A systematic approach for the development of heterogeneous mechanisms is applied and evaluated for the catalytic partial oxidation of methane over platinum (Pt) and rhodium (Rh). The derived mechanisms are self-consistent and based on a reaction class-based framework comprising variational transition state theory (VTST) and two-dimensional collision theory for the calculation of pre-exponential factors with barrier heights obtained using the unity bond index–quadratic exponential potential (UBI–QEP) method. The surface chemistry is combined with a detailed chemistry for the gas phase, and the accuracy of the approach is evaluated over Pt for a wide range of stoichiometries (0.3 ≤ ϕ ≤ 4.0), pressures (2 ≤ P (bar) ≤ 16), and residence times. It is shown that the derived mechanism can reproduce experimental data with an accuracy comparable to that of the prevalent collision theory approach and without the reliance on experimental data for sticking coefficients. The derived mechanism for Rh shows encouraging agreement for a similar set of conditions, and the robustness of the approach is further evaluated by incorporating partial updates via more accurate DFT-determined barrier heights. Substantial differences are noted for some channels (e.g., where reaction progress is strongly influenced by early transition states) though the impact on the overall agreement with experimental data is moderate for the current systems. Remaining discrepancies are explored using sensitivity analyses to establish key parameters. The study suggests that the overall framework is well-suited for the efficient generation of heterogeneous reaction mechanisms, that it can serve to identify key parameters where high accuracy ab initio methods are required, and that it permits the inclusion of such updates as part of a gradual refinement process.