The structure and catalytic properties of the ultrafine Co-Ce-O complex oxide particle catalysts for selective oxidation of 4-methylphenol(PMP) to 4-hydroxybenzaldehyde(PHB) have been studied by using TEM, XRD, XPS, BET surface area measurements and microreactor tests. It has been shown that the structure, composition and partical size of the ultrafine oxide particles exert great influences on the catalytic properties. Increasing cobalt content in the complex oxide. The catalytic activity for selective oxidation of PMP to PHB increases firstly and then decreases remarkably. It has been found that the higher activity of the ultrafine Co-Ce-O complex oxide particles catalysts for selective oxidation of PMP to PHB was not only correlated to their higher surface areas of the ultrafine particles but also correlated to the interaction between Co oxide and Ce oxide. Thermal treatments at higher temperatures result in sintering of the particles and destroy the interaction between Co oxide and Ce oxide, leading to remarkable decrease in the catalytic selective oxidation activity.