Single metal atom catalysts exhibit extraordinary activity in a large number of reactions, and some two-dimensional materials (such as graphene and h-BN) are found to be prominent supports to stabilize single metal atoms. The CO oxidation reaction on single Pd atoms supported by two-dimensional h-BN is investigated systematically by using dispersion-corrected density functional theory study. The great stability of the h-BN supported single Pd atoms is revealed, and the single Pd atom prefers to reside at boron vacancies. Three proposed mechanisms (Eley–Rideal, Langmuir–Hinshelwood, and a “new” termolecular Eley–Rideal) of the CO oxidation were investigated, and two of them (the traditional Langmuir–Hinshelwood mechanism and the new termolecular Eley–Rideal mechanism) are found to have rather small reaction barriers of 0.66 and 0.39 eV for their rate-limiting steps, respectively, which suggests that the CO oxidation could proceed at low temperature on single Pd atom doped h-BN. The current study will help to understand the various mechanisms of the CO oxidation and shed light on the design of CO oxidation catalysts, especially based on the concept of single metal atoms.