The structure sensitivity of acetylene hydrogenation was studied over size-controlled cubic and octahedral Pd nanocrystals (NCs) supported on ZnO and SiO2. Acetylene hydrogenation was found to be structure sensitive [with Pd(111) in octahedra being more active than Pd(100) in cubes]. However, the response was found to vary depending on the redox properties of the support. The catalytically active and selective palladium carbide (PdCx) phase was readily formed on the SiO2-supported Pd NCs (much faster on cubes than on octahedra), whereas a markedly less active PdZn phase was preferentially formed on the ZnO-supported Pd nanocrystals. Here we show that the structure sensitivity of a chemical reaction is a complex phenomenon that originates from the reconstruction of the active phase in response to the reactive environment, which is ultimately determined by the support used.