Better emission control of internal combustion engines can be achieved by more efficient catalytic hydrocarbon combustion at low temperatures. For a knowledge-based design of suitable catalyst candidates, a promising approach integrates theoretical models with experimental benchmarks. Studying catalytic hydrocarbon combustion theoretically is challenging, however, since hydrocarbon reaction networks are complex: even simple C2 combustion reactions include hundreds of possible elementary steps. Herein, we present a paradigm to address this challenge by (1) supplementing experimental insights with extensive density functional theory studies to derive a proxy combustion reaction network; (2) using machine learning-enhanced transition state search to rigorously scan reaction coordinates; and (3) combining ab initio thermodynamics, microkinetic modeling, and a degree of rate control analysis to unveil adsorbate coverage effects and rate-limiting reaction steps. Our systematic approach permits modeling a reaction as complex as propene combustion on palladium while maintaining the computationally efficient mean-field approximation. Using a partially oxygen-covered palladium surface model, which includes adsorbate–adsorbate interactions, we predict experimentally measured rates within 2 orders of magnitude without parameter fitting. The corresponding degree of rate control analysis yields that the second and penultimate dehydrogenation step in the reaction network limit the rate of propene combustion on palladium.