As an integral part in methanation, CH4 formation from successive hydrogenation of atomic C was systematically studied over stepped Ni(211) and Ni3Fe(211) surfaces via periodic density functional theory calculations. The effect of surface composition was explicitly examined by taking into account of two termination structures of Ni3Fe(211) (the surfaces with NiNi- and NiFe-type step are denoted as Ni3Fe(211)-AA and Ni3Fe(211)-AB, respectively). Both alloyed surfaces are found to benefit the initial C hydrogenation through enhancing H adsorption as well as weakening the binding strength of C. Because CH2 generation and subsequent CH2 hydrogenation favor different sites over such stepped surfaces, the step of CH2 migration was proposed and incorporated into the mechanism. The hydrogenation reactions manifest significant structural sensitivity since Ni3Fe(211)-AB is superior to Ni3Fe(211)-AA in lowering the overall potential energy surfaces towards CH4 formation. In combination with our previous work focusing on CO activation and dissociation, the present results confirmed the improved activity of Ni3Fe alloy catalyst for CO methanation suggested experimentally and the Ni3Fe(211)-AB termination is further identified to dominate the promoting effect. A newly proposed Bronsted Evans Polanyi relationship is also found to hold for the successive hydrogenation steps herein. (C) 2016 Hydrogen Energy Publications LLC. Published by Elsevier Ltd. All rights reserved.