The aim of this study is to explore the mechanisms of CO oxidation to CO2 over some C59X heterofullerenes (X = B, P, Si and S) through systematic dispersion-corrected density functional theory calculations. The adsorption energy of O2 over these fullerenes becomes more negative in the order of C59S < C59B < C59P < C59Si. According to our results, the CO oxidation reaction cannot take place over C59B and C59S due to the poisoning of the active site of these surfaces by CO. The oxidation of first CO molecule over C59Si and C59P proceeds via the Langmuir–Hinshelwood mechanism.