Reforming of hydrocarbon fuels is one of the most important heterogeneous catalytic processes. Particularly appealing is potential development of catalysts that could be used as internal reforming anodes in solid oxide fuel cells (SOFCs). Current reforming catalysts such as Ni, however, suffer from two major problems: (i) coke formation that deactivates the catalyst and (ii) sulfur poisoning of the catalyst. These problems are particularly challenging for logistic fuels such as JP-8 that are rich in heavy hydrocarbons and sulfur compounds. To prevent carbon deactivation, we have investigated various Ni-based alloy materials in steam reforming of a number of hydrocarbon fuels. Our objective was to identify those alloys that are carbon-tolerant and that can operate with low steam concentrations. We have utilized density functional theory (DFT) calculations to identify, based on the understanding of underlying chemical transformations that govern carbon poisoning, potential carbon-tolerant alloy catalysts. The DFT calculations were coupled with reactor studies and an assortment of characterization techniques to test the promising alloy catalysts. These studies have led to the identification of alloy Ni catalysts that are superior to monometallic Ni catalysts.