The role of particle-substrate interactions on the reactivity of bimetallic nanostructures is investigated in the case of Au-Pd core-shell nanoparticles supported on Vulcan XC-72R (Vulcan). Core-shell nanostructures (CS) featuring 19 nm Au cores and Pd shells with thicknesses between ca. 1 and 10 nm were synthesized by controlled colloidal methods and subsequently incorporated in the carbon support. X-ray diffraction, energy dispersive X-ray analysis, and high resolution transmission electron microscopy confirmed the CS nature of the nanostructures, which remain unaffected upon incorporation onto the carbon matrix. Their electrochemical properties toward CO and HCOOH electro-oxidation were studied, using cyclic voltammetry and chronoamperometry. The results show that the CO stripping potential becomes independent of the average Pd lattice strain in the case of Vulcan supported CS. This behavior is significantly different to the trend observed in CS assemblies at In-doped SnO2 electrodes. Formic acid oxidation is also strongly affected not only by the thickness of the Pd nanoshell but also by the support. These reactivity trends are discussed in terms of strain (geometric) effects, CS crystalline structure, and substrate effects on the onset potential for the formation of oxygenated species at the catalyst surface.