In this study, we investigated the catalytic performance of Ru nanoparticles (NPs) supported on Ni-nanowires for the first time. This appears to be a highly efficient catalyst for low-temperature methanation, e.g., ca. 100% conversion and 100% of CH4 selectivity can be achieved at ca. 179 °C, while the turnover frequency (TOF) value was 2479.2 h−1. At the same time, the onset of a reaction was observed at a temperature as low as 130 °C. The comparison of nano-Pd and nano-Ru supported on Ni-nanowires enabled us to prove that oxidized surface metals are highly important for the high activity of the investigated nano-Ru@nanowired-Ni. Moreover, similar to the microscopic Sabatier rule, which indicates that some optimal reactivity level of a catalyst exists, we showed that Ni-nanowires (a higher specific surface area than a standard metal surface, e.g., in the form of a metal foam, but lower than nano-sized materials) significantly enhances the performance of the Ru-Ni catalytic system.