Trehalose is a widely prevalent disaccharide that acts as a cellular stress protectant and functions as an energy source that enters central carbon metabolism when broken down. The evolution and distribution of trehalose breakdown pathways across kingdoms of life is not well studied, and therefore the ability of different organisms to consume trehalose as a carbon source is unknown. In this study, we build a comprehensive evolutionary analysis of the four known trehalose breakdown pathways—trehalase (acid, neutral, glycosyl hydrolase 15), trehalose phosphorylases (TP, treP), and trehalose specific phosphotransferases (PTS), by studying their distributions across ∼3,800 prokaryotic and eukaryotic genomes. Our study suggests the presence of trehalase in the last eukaryotic common ancestor, and reveals near-universal presence of trehalase in eukaryotes, except in all birds where trehalase was lost in the first bird ancestor. Fungi alone retain additional TPs in addition to trehalase. In contrast, while trehalose breakdown in prokaryotes is highly sporadic, it can occur via multiple, independently evolved pathways, including trehalase, the trehalose-specific PTS and TP. Finally, we observe that a subset of fast-growing Gammaproteobacteria retain the trehalose specific PTS, the loss of which reduces growth in Escherichia coli. Overall, our findings uncover the evolutionary landscape of trehalose breakdown, and use of this versatile disaccharide as an energy reserve in different kingdoms of life.