Cell-cell communication (CCC) is crucial for cellular function and tissue homeostasis. Existing methods for protein-oriented CCC detection often overlook metabolite-mediated CCC (mCCC), and adapting them to mCCC analysis is challenging due to fundamental differences in the underlying biological mechanisms. To fill this gap, we developed MEBOCOST, an algorithm built on scRNA-seq and metabolic flux balance analysis to detect mCCC among single cells. Comprehensive benchmarking analyses based on simulation, spatial, CRISPR screen, and clinical patient data demonstrated the robustness of MEBOCOST in detecting biologically significant mCCC events. We applied MEBOCOST to scRNA-seq datasets of human white adipose tissues and unraveled macrophages were the predominant source of mCCC reprogramming in obese patients. Moreover, analysis in mice brown adipose tissue successfully recapitulated known and further uncovered new mCCC events, including a glutamine-mediated endothelial-to-adipocyte communication, which was experimentally verified to regulate adipocyte differentiation. Therefore, MEBOCOST is a valuable tool for researchers investigating mCCC in diverse biological contexts and disease samples. MEBOCOST is freely available at https://github.com/kaifuchenlab/MEBOCOST.