Density Functional Theory (DFT) calculations were utilized to study the surface chemistry of carbon atoms on Ni. These studies demonstrated that there is a strong thermodynamic driving force to form sp2-bonded carbon networks. It is believed that these extended carbon structures diminish the hydrocarbon reforming activity of Ni catalysts. We have further utilized DFT to search for Ni-containing alloy catalysts that might be more carbon-tolerant than monometallic Ni, i.e., that have a lower propensity to form the extended carbon networks. These studies have yielded a promising alloy formulation. We have tested the alloy under steady-state conditions in the steam reforming of various hydrocarbons. The reactor studies support the predictions of the first principles calculations.