The classical asymptotic theory describing the structure of stoichiometric methane–air flames, introduced by Peters and Williams, has been extended to describe the structure of stoichiometric methane–hydrogen–air flames. The theory predicts a decreasing inner-layer temperature, while the adiabatic flame temperature increases slightly with increasing amount of hydrogen in the fuel. These changes together lead to an increasing burning velocity as a function of the amount of hydrogen in the fuel mixture. The predicted variations are compared with numerical results; the burning velocity is also compared with experiments and the agreement is reasonable. To demonstrate in an independent way that the decrease in the inner-layer temperature dominates the change in flame structure and burning velocity, additional measurements of the influence of heat loss on the burning velocity of methane–hydrogen–air flames are carried out. The effective activation energy governing this behavior shows a decrease as a function of the amount of hydrogen, confirming the prediction of the theory that the inner-layer temperature decreases with increasing amount of hydrogen. The derived analytical expressions can be used to guide the adaption of combustion systems running on natural gas when hydrogen is added to the fuel.