Abstract: This study systematically investigated the catalytic gasification of two distinct petroleum coke (PC) using magnesium-based tailings (MT) as the catalyst. The research objectives focused on comparative analysis of gasification reactivities and elucidation of carbon microstructure evolution during PC gasification. Experimental results demonstrate that PC-B (derived from Liaohe Oilfields delayed coking) exhibited significantly higher gasification activity than PC-A (from Karamay Oilfields delayed coking), with aromatic C–H content and polycondensation index showing stronger correlations with reactivity than graphitization parameters. Notably, the MT catalyst exhibited material-dependent catalytic behaviors during gasification. MT catalyst enhanced structural ordering in PC-B by: (i) developing denser aromatic carbon layers, (ii) improving microcrystalline alignment, and (iii) elevating graphitization degree. These structural modifications contrasted sharply with PC-A’s response, where MT introduction generated active MgO species in the ash phase, boosting gasification reactivity. Conversely, in PC-B ash systems, MgO preferentially reacted with Al2O3 to form inert MgAl2O4 spinel, effectively deactivating the catalyst. Kinetic investigations validated the shrinking core model (SCM) as the dominant mechanism, with calculated activation energies of 172.12 kJ/mol (PC-A + 5% MT) and 137.19 kJ/mol (PC-B + 5% MT).