Pd/TiO2 and Pd/CeO2 were reported to be very active to destruct toluene. Combination of TiO2 and CeO2 is an interesting candidate to achieve a catalyst with higher activity. In this study, a series of Pd/CeO2-TiO2 catalysts with various Pd loadings were prepared. CeO2-TiO2 was prepared by impregnation of aqueous solution of cerium nitrate into TiO2 support. It was then calcined at 400 °C. Pd was loaded by incipient-wetness impregnation method. The Pd loadings in all samples were fixed at 0.5 wt.%. The catalysts were characterized by powder X-ray diffraction, transmission electron microscopy, high resolution transmission electron microscopy, temperature-programmed reduction of hydrogen, and X-ray photoelectron spectroscopy. The catalysts were tested for total oxidation of toluene. The feed concentration of toluene was 8.564 g/m3 (2085 ppm), with GHSV = 10, 000 h-1. Pd particle sizes were 3-5 nm and well-dispersed on the support. CeO2 on TiO2 was easier to reduce than the bulk CeO2, therefore it could enhance the activity of VOC destruction. Pd/CeO2-TiO2 was more active than Pd/CeO2 and Pd/TiO2. Pd/CeO2-TiO2 with Ce/Ti ratio of 2/8 was very active for toluene destruction, due to its lower oxygen reduction temperature of ceria and higher concentration of Pd0.