Steam reforming is a process that converts hydrocarbon fuels into hydrogen and oxygenated carbon species. This process is important not only for the catalytic hydrogen production but also for direct electrochemical reforming over high temperature fuel cells such as Solid Oxide Fuel Cells (SOFCs). One of the main problems associated with the process is that the commonly used anode reforming catalysts, such as Ni supported on oxides, deactivate due to carbon poisoning. We have utilized Density Functional Theory (DFT) calculations to study carbon chemistry on Ni and Ni-containing alloys. The main objective of these studies was to develop molecular insights regarding carbon poisoning on Ni and to utilize this molecular information to identify possible carbon-tolerant alternatives to Ni. The DFT calculations showed that Ni surface alloys had lower tendencies towards carbon poisoning compared to monometallic Ni. The identified alloy catalysts were tested in steam reforming of methane, propane, isooctane, and other hydrocarbon fuels. The alloy catalysts showed favorable performance compared to monometallic Ni catalysts.