The catalytic partial oxidation of iso-octane and sulfur-free gasoline was studied over Ni-based catalysts supported on CeO2-, La2O3-, ZrO2-, Al2O3-, and their combinations prepared by precipitation and surfactant assisted methods. A comparison of their performance was also made with a Ni/Al2O3 catalyst for the oxidation of pure gasoline surrogate, that is, iso-octane. These catalysts were characterized by specific surface area, temperature programmed reduction (TPR), H-2 chemisorption, and X-ray diffraction, and their catalytic performance was tested in a fixed bed tubular reactor. The characteristics of the catalysts were then correlated with their performance. The use of CeO2 as a support prepared by a surfactant approach was found to produce the most stable catalyst for the partial oxidation of both iso-octane and gasoline. TPR results showed that the stability of CeO2 is derived from its enhanced reducibility at lower temperatures as compared to either similar support prepared by other methods or different support prepared by the same method or other methods. Brunauer-Emmett-Teller surface area measurements indicated a 100% enhancement in the CeO2 support specific surface area when the surfactant method was used during preparation as compared with the precipitation method. On the basis of a stability test, 5% Ni CeO2 was found to be the most stable catalyst.