Solid oxide fuel cells (SOFCs) have been attracting remarkable attention as one of the most promising green energy conversion devices in the recent years. However, a high susceptibility of commonly used Ni-based anodes to carbon coking is a major challenge to the successful commercialization of SOFCs. In this study, a robust anode with Ni/TiO2−δ nano-network interfaces is reported, for low-cost SOFCs working at intermediate temperatures. This anode demonstrates an acceptable power density, and good stability with humidified (3% H2O) methane. X-ray diffraction (XRD) Rietveld refinement, X-ray photoelectron spectroscopy (XPS), electron paramagnetic resonance (EPR), and high resolution transmission electron microscopy (HRTEM) images reveal that the Ni/TiO2−δ network-composite anode forms from the in-situ reductive decomposition of NiTiO3. Numerous Ni/TiO2−δ interfaces that facilitate the water adsorption and the water-mediated carbon-removing reactions form during this decomposition process. Density functional theory calculations predict that at the Ni/TiO2−δ interfaces, the dissociated OH from H2O (adsorbed on TiO2−δ) reacts with C (locating on Ni) to produce CO and H species, which are then electrochemically oxidized (combined with O2−) to CO2 and H2O at the triple-phase boundaries of the anode.