The decomposition of methane (CH4) is a catalytically important reaction in the production of syngas that is used to make a wide spectrum of hydrocarbons and alcohols, and a principal carbon deposition pathway in methane reforming. Literatures suggest that stepped Ni surface is uniquely selective toward methane decomposition to atomic C, contrary to other catalysts that favor the CH fragment. In this paper, we used dispersion-corrected density functional theory-based first principles calculations to identify the electronic factors that govern this interesting property of stepped Ni surface. We found that the adsorption of atomic C on this surface is uniquely characterized by a 5-coordinated bonding of C with Ni atoms from both the surface and subsurface layers. Comparison with Ru surface indicates the importance of the subsurface atoms of stepped Ni surface on its selectivity toward methane decomposition to atomic C. Interestingly, we found that substituting these subsurface atoms with other elements can dramatically change the reaction mechanism of methane decomposition, suggesting a new approach to catalyst design for hydrocarbon reforming applications.