The evidence of the carbon bulk diffusion mechanism, operating in catalytic carbon gasification, is summarized. Linking visual and structural observations (transmission electron microscopy and X-ray diffraction) with comprehensive kinetic studies offers a good basis to understand the details of the phenomenological behavior. The role of the catalyst nanoparticles in catalytic coal/coke gasification and in graphene reactions is briefly reviewed. Knowledge of the solid-state phases operating under steady-state reaction and of the “sintering like” catalyst-carbon contact is essential to understand the most likely reaction sequence: 1st step - carbon dissolution; 2nd step - C bulk diffusion; 3rd step - surface reaction of emerging C atoms with the reactant gas. Kinetics and preliminary solid-state changes observed in graphite gasification and in coke/coal gasification leads to the conclusion that they follow the same mechanism. Using an analogy with proton exchange membranes in fuel cells: catalytic carbon gasification is promoted by carbon exchange moving nanoparticles. A better understanding of the mechanism may lead to improvements in industrial processes.