Extensive efforts to develop a solid-oxide fuel cell for transportation, the bottoming cycle of a power plant, and distributed generation of electric energy are motivated by a need for greater fuel efficiency and reduced air pollution. Barriers to the introduction of hydrogen as the fuel have stimulated interest in developing an anode material that can be used with natural gas under operating temperatures 650 degrees C < T < 1000 degrees C. Here we report identification of the double perovskites Sr2Mg(1-x)MnxMoO(6-delta) that meet the requirements for long-term stability with tolerance to sulfur and show a superior single-cell performance in hydrogen and methane.