Coke formation poses a significant obstacle in the direct conversion of methane into valuable chemicals such as ethylene, benzene, and hydrogen via methane dehydro-aromatization (MDA). At the elevated temperatures necessary for this reaction, coke is the thermodynamically favored product, causing rapid catalyst deactivation and hence necessitating frequent catalyst regeneration. Successful industrial implementation of MDA requires the advancement of catalyst regeneration processes and a comprehensive understanding of coke formation to enhance catalyst performance. Here, we examined the types of coke generated during MDA over a Fe-ZSM-5 catalyst and their impact on deactivation. By combining reactivity studies using catalysts with carefully controlled coke populations with the characterization of the catalyst via XRD, H2-TPR, and pyridine FTIR, we find that soft coke is formed at the Brønsted acid sites, resulting in loss of selectivity, while hard coke is formed at the metal sites causing a loss of activity. While soft coke can be removed at low regeneration temperatures, the removal of hard coke requires harsh conditions which compromise catalyst stability. An investigation into the use of CO2 as an alternative, mild oxidant for catalyst regeneration, however, shows that the mild oxidation strength of CO2 requires even higher regeneration temperatures and hence irreversible loss of Brønsted acid sites.