Sulfur-containing molecules are common impurities in fuels and oil-derived chemical feedstocks. In our industrial society, these impurities have a negative impact in the petrochemical industry and degrade the quality of the air by forming sulfur oxides (SOx) during the burning of fuels and by poisoning the catalysts used in vehicle catalytic converters. Hydrodesulfurization (HDS) is one of the largest processes in petroleum refineries where sulfur is removed from the crude oil. The current HDS catalysts cannot provide fuels with the low content of sulfur required by new environmental regulations. Transition metal carbides and phosphides have shown a tremendous potential as highly active HDS catalysts. At a microscopic level, it is not well understood how these new catalysts work. Recently, density-functional calculations and synchrotron-based techniques (high- resolution photoemission, x-ray absorption spectroscopy, time-resolved x-ray diffraction) have been used to study the chemistry of S-containing molecules on single-crystal surfaces and nanoparticles of metal carbides and phosphides. These studies reveal that the C and P sites in the catalysts play a complex and important role in HDS reactions and cannot be considered as simple spectators. They moderate the reactivity of the metal centers (allowing the cleavage of C-S bonds, but preventing the formation of strong metal-sulfur bonds) and provide bonding sites for the H adatoms necessary for the hydrogenation of S and CxHy fragments.