The plasma-arc (PA) method was applied for the highly efficient synthesis of Pd/Ce–Sn–O catalysts for CO oxidation. Using the PA sputtering of a graphite electrode together with Pd, Ce and Sn metallic components in inert atmosphere, a PdCeSnC composite was obtained. After the subsequent calcination in oxygen over the temperature range of 600–1000 °C, the initial composites were transformed into active catalysts of CO oxidation at low temperatures (LTO CO). Catalytic testing showed that these PA-prepared Pd/Ce–Sn–O catalysts were characterized by unusually high thermal stability. The catalysts demonstrated the excellent LTO CO performance after calcination at 1000 °C. According to the XRD and HRTEM observations, the Pd/Ce–Sn–O catalysts can be described as heterogeneous structures consisting of small CeO2 and SnO2 particles that interact with each other, forming extended grain boundaries and a composite structure. The TPR-CO and XPS methods detected highly dispersed Pd species in the active catalysts, namely Pd2+ in the lattice of ceria (a Pd-ceria solid solution) and the PdOx clusters on the surface. Deactivation of the Pd/Ce–Sn–O is governed by decomposition of the Pd-ceria solid solution accompanied by the sintering of the PdOx clusters and formation of the metallic and oxide palladium nanoparticles. Oxygen species with high mobility in the Pd/Ce–Sn–O catalyst were detected by a TPR-CO method. The amount of the highly mobile oxygen species is in five times higher for the Pd/Ce–Sn–O catalyst then for the Pd/CeO2 sample. Promising perspectives of the plasma-arc application for catalyst the synthesis of with improved properties are discussed.