Diabetes mellitus is associated with increased cardiovascular disease (CVD) related morbidity, mortality and death. Exercise capacity in persons with type 2 diabetes has been shown to be predictive of cardiovascular events. In this study, we used the data from the prospective randomized LOOK AHEAD study and used machine learning algorithms to help predict exercise capacity (measured in Mets) from the baseline data that included cardiovascular history, medications, blood pressure, demographic information, anthropometric and Dual-energy X-Ray Absorptiometry (DXA) measured body composition metrics. We excluded variables with high collinearity and included DXA obtained Subtotal (total minus head) fat percentage and Subtotal lean mass (gms). Thereafter, we used different machine learning methods to predict maximum exercise capacity. The different machine learning models showed a strong predictive performance for both females and males. Our study shows that using baseline data from a large prospective cohort, we can predict maximum exercise capacity in persons with diabetes mellitus. We show that subtotal fat percentage is the most important feature for predicting the exercise capacity for males and females after accounting for other important variables. Until now, BMI and waist circumference were commonly used surrogates for adiposity and there was a relative under-appreciation of body composition metrics for understanding the pathophysiology of CVD. The recognition of body fat percentage as an important marker in determining CVD risk has prognostic implications with respect to cardiovascular morbidity and mortality.