Carbon deposition and sintering of active components such as nano particles are great challenges for Ni-based catalysts for CO methanation to generate synthetic natural gas from syngas. Facing the challenges, bimetallic catalysts with different Fe content derived from layered double hydroxide containing Ni, Fe, Mg, Al elements were prepared by co-precipitation method. Nanoparticles of Ni-Fe alloy were supported on mixed oxides of aluminium and magnesium after calcination and reduction. The catalysts were characterized by Brunner-Emmett-Teller (BET), X-ray diffraction, hydrogen temperature programmed reduction, inductively coupled plasma, X-ray photoelectron spectroscopy, transmission electron microscopy and thermogravimetric techniques, and their catalytic activity for CO methanation was investigated. The results show that the Ni-Fe alloy catalysts exhibit better catalytic performance than monometallic catalysts except for the Ni4Fe-red catalyst. The Ni2Fe-red catalyst shows the highest CO conversion (100% at 260–350 °C), as well as the highest CH selectivity (over 95% at 280–350 °C), owing to the formation of Ni-Fe alloy. In stability test, the Ni2Fe-red catalyst exhibits great improvement in both anti-sintering and resistance to carbon formation compared with the Ni0Fe-red catalyst. The strong interaction between Ni and Fe element in alloy and surface distribution of Fe element not only inhibits the sintering of nanoparticles but restrains the formation of Ni clusters.