Non-oxidative methane dehydroaromatization is a promising reaction to directly convert natural gas into aromatic hydrocarbons and hydrogen. Commercialization of this technology is hampered by rapid catalyst deactivation because of coking. A novel approach is presented involving selective oxidation of coke during methane dehydroaromatization at 700 °C. Periodic pulsing of oxygen into the methane feed results in substantially higher cumulative product yield with synthesis gas; a H2/CO ratio close to two is the main side-product of coke combustion. Using 13C isotope labeling of methane it is demonstrated that oxygen predominantly reacts with molybdenum carbide species. The resulting molybdenum oxides catalyze coke oxidation. Less than one-fifth of the available oxygen reacts with gaseous methane. Combined with periodic regeneration at 550 °C, this strategy is a significant step forward, towards a process for converting methane into liquid hydrocarbons.