Binary Pd-based nanostructures are highly efficient electrocatalysts for various applications. However, the alloy effect and electrolyte pH on CO oxidation (COoxid) remain ambiguous. This work presents a facile fabrication of porous PdM (M = Cu, Au, and Mn) spongy-like nanostructures via an aqueous-phase chemical reduction method for the electrocatalytic COoxid. The fabrication process comprises the direct ice-chemical reduction of binary metal precursors by sodium borohydride (NaBH4), without the need for supports, organic solvents, surfactants, and heating, but driven by the burst nucleation and coalescence growth mechanism. The COOxid activities and stabilities of PdM nanostructures were superior to commercial Pd/C catalysts in acidic, alkaline, and neutral electrolytes, due to the porous morphology, alloy effect, clean surface, and absence of the support, but PdCu has the highest COOxid activity. Mainly, the COOxid activity of PdCu nanocrystals was higher than those PdMn, AuPd, and Pd/C catalysts by at least 1.74, 1.14, and 2.63-folds in H2SO4, KOH, and NaHCO3, respectively, in addition to their excellent durability for 1000 cycles. This implies that PdCu alloy with a higher strain is preferred for promoting the COOxid, due to the greater electron/mass transport, higher active surface area, and greater oxophilicity of Cu-enabled fast H2O activation/dissociation at a lower potential. This study may allow formation of other self-standing Pd-alloys for electrocatalytic COOxid.