The catalytic activity of a 4 monolayer deposit of Pd on a Ni(110) surface toward the hydrogenation of ethylene is investigated by using gradient-corrected periodic density functional calculations. The Pd/ Ni(l 10) surface is strongly nanostructured, due to the anisotropic stress induced by the Ni(110) substrate on the Pd layer. A kinetic analysis, based on the investigation of the optimal reaction pathway for the hydrogenation of ethylene to ethane, is presented, allowing a comparison between Pd/Ni(110) and pure Pd(110) surfaces. The calculated activation energies allow one to reproduce the experimental result, which shows that the Pd/Ni(110) surface is about 30 times more active than the pure Pd(110) surface. This marked increase of the catalytic activity is a consequence of the specific nanostructure of the Pd/Ni(110) surface. By examining the structure of the adsorbed species and of the transition states and by analyzing the electronic properties, we show that this rate increase can be associated to the fact that the ethylene adsorption energy in the first hydrogenation step and the ethyl-hydrogen coadsorption energy in the second step are both much lower on Pd/Ni(110) than on pure Pd(110).