Colloidal suspensions of AuxPd1-x nanoalloys were prepared via hydrazine co-reduction of [AuCl4]− and [PdCl4]2− complex anions in aqueous solution. High molecular weight polymeric compounds polyvinylpyrrolidone (PVP), polyvinyl alcohol (PVA), and cryptoionic surfactants (AF-6 and AF-12 neonols, Triton X-100) were used as surface capping agents. Nanoparticles prepared under different experimental conditions were immobilized on γ-Al2O3 supports. The removal of the capping agents from the surface of the active particles was achieved through calcination of samples in oxidative atmosphere (air, 500 °C). This pretreatment of the catalysts significantly enhances their performance. Powder XRD, TEM, and EDX were employed to characterize the structure, size, and composition of the AuxPd1-x/γ-Al2O3 catalysts. The immobilized particles consist of uniformly mixed alloys having multi-domain face-centered cubic structure with typical crystallite size of 3–6 nm. The activity of the prepared samples was examined with temperature-programmed CO oxidation reaction (TP-CO+O2). Triton X-100 surfactant is superior in a number of parameters. Among all AuxPd1-x/γ-Al2O3 catalysts tested, the one stabilized with Triton X-100 (0.4%Au-0.2%Pd@Triton X-100) was found to have the highest activity for conversion of CO into CO2.