NiCoMgO x and NiCoMgCeO x on commercial low surface area zirconia–haffnia catalysts have unusually high thermal stability (⩾2000°C) for syngas generation via the methane partial oxidation process (J. Catal., 233, 36, 2005). Herein we report the results on accelerated sulfur deactivation (0.74mol% sulfur in feed) and corresponding regeneration (at 800°C in 1:1 O 2 +N 2 flow) over these catalysts. The NiCoMgCeO x catalyst, due to a larger mobility of lattice oxygen, showed a considerably higher resistance to sulfur poisoning; the higher mobility of the lattice oxygen in case of the NiCoMgCeO x catalyst may be related to the presence of CeO 2 . During the deactivation process, the selectivity for H 2 was decreased to a much greater extent than that for CO. Regeneration studies showed that even after complete deactivation of the catalysts, the original activity/selectivity of both the catalysts could be completely restored after a simple regeneration process. Based on their exceptionally high thermal stability, high activity/selectivity and easily regenerability, the NiCoMgO x and NiCoMgCeO x catalysts appear to be very promising candidates for the CPOM process.