Hydrogenolysis of complex heteroatom-containing organic molecules plays a large role in upgrading fossil- and biomass-based fuel and chemical feedstocks, such as hydro-deoxygenation and desulfurization. Here, we present a fundamental study contrasting the cleavage of C-X bonds in ethane, methylamine, methanol, methanethiol, and chloromethane on group 8-11 transition metals (Ru, Os, Co, Rh, Jr, Ni, Pd, Pt, Cu, Ag, and Au) using density functional theory (DFT). Previous kinetic and DFT studies have shown that hydrogenolysis of unsubstituted C-C bonds in alkanes occur via unsaturated intermediates (e.g., *CHCH* for ethane) after a series of quasi-equilibrated dehydrogenation steps that weaken the C-C bond by creating C-metal bonds. However, the effects of the substituent group in CH3XHn on the required degree of unsaturation to cleave the C-X have not been systematically studied and are critical to understanding heteroatom removal. DFT-predicted free energy barriers indicate that the carbon atom in C-X generally cleaves after the removal of 2 H atoms (to form CH*) on group 8-10 metals regardless of the identity of the metal or the heteroatom. Group 11 metals (coinage metals: Cu, Ag, and Au) generally deave the C-X bond in the most H-saturated intermediates with barriers close to thermal activation of C-X in gaseous CH3CHn molecules. The N-leaving group in C-N cleavage depends on the metal identity as it can leave fully dehydrogenated (as N*) on group 8 metals and partially or fully hydrogenated (as NH* or NH2*) on group 9-11 metals. Although O and S are both group 16 elements, C-S bonds always deave to form S* (losing one H), while C-O bonds generally deave to form OH* (without preceding H removal). Cl does not have H atoms to be removed before C-Cl cleavage in CH3Cl, and thus the C atom sacrifices an additional H atom to weaken the C-Cl bond on group 8 metals. This study of heteroatom removal from simple organic molecules is the first step to providing fundamental insights into H-2-based upgrading of more complex organic molecules.