Palladium and cerium oxide nanoparticles obtained by pulsed laser ablation (PLA) in liquid (water or ethanol) have been used as nanostructured precursors for the synthesis of composite Pd/CeO2 catalysts. The initial mixture of Pd and CeO2 nanoparticles does not show catalytic activity at temperatures lower than 100 °C. It has been found that the composites prepared by PLA in alcohol are easily activated by calcination in air at 450-600 °C, demonstrating a high level of activity at room temperature. Application of XRD, TEM and XPS reveals that laser ablation in water leads to the formation of large and well-crystallized nanoparticles of palladium and CeO2, whereas ablation in alcohol results in the formation of much smaller PdCx nanoparticles. The activation of the composites takes place due to the strong Pd-ceria interaction which occurs more easily for highly dispersed defective particles obtained in alcohol. Such an interaction implies the introduction of palladium ions into the ceria lattice with the formation of a mixed phase of PdxCe1-xO2-x-δ solid solution at the contact spaces of palladium and cerium oxide nanoparticles. TPR-CO and XPS data show clearly that on the surface of the PdxCe1-xO2-x-δ solid solution the oxidized PdOx(s)/Pd-O-Ce(s) clusters are formed. These clusters are composed of highly reactive oxygen which is responsible for the high level of catalytic activity in LTO CO.