Cardiorespiratory fitness (CRF) represents a strong predictor of all-cause mortality and is strongly influenced by regular physical activity (PA). However, the biological mechanisms involved in the body’s adaptation to PA remain to be fully elucidated. The aim of this study was to systematically examine the relationship between CRF and plasma metabolite patterns in 252 healthy adults from the cross-sectional Karlsruhe Metabolomics and Nutrition (KarMeN) study. CRF was determined by measuring the peak oxygen uptake during incremental exercise. Fasting plasma samples were analyzed by nuclear magnetic resonance spectroscopy and mass spectrometry coupled to one- or two-dimensional gas chromatography or liquid chromatography. Based on this multi-platform metabolomics approach, 427 plasma analytes were detected. Bi- and multivariate association analyses, adjusted for age and menopausal status, showed that CRF was linked to specific sets of metabolites primarily indicative of lipid metabolism. However, CRF-related metabolite patterns largely differed between sexes. While several phosphatidylcholines were linked to CRF in females, single lyso-phosphatidylcholines and sphingomyelins were associated with CRF in males. When controlling for further assessed clinical and phenotypical parameters, sex-specific CRF tended to be correlated with a smaller number of metabolites linked to lipid, amino acid, or xenobiotics-related metabolism. Interestingly, sex-specific CRF explanation models could be improved when including selected plasma analytes in addition to clinical and phenotypical variables. In summary, this study revealed sex-related differences in CRF-associated plasma metabolite patterns and proved known associations between CRF and risk factors for cardiometabolic diseases such as fat mass, visceral adipose tissue mass, or blood triglycerides in metabolically healthy individuals. Our findings indicate that covariates like sex and, especially, body composition have to be considered when studying blood metabolic markers related to CRF.