Background: The assessment of fat mass and fat-free mass in relation to the symptom-limited maximal exercise duration (Max dur) of a treadmill test allows for insight into the association of body composition with treadmill performance potential. Objective: We investigated the complex associations between fat mass and fat-free mass and Max dur in a population setting. Design: The Max dur of a graded exercise treadmill test and body composition by dual-energy X-ray absorptiometry were estimated in 2413 black and white men and women aged 38-50 y from the Coronary Artery Risk Development in Young Adults (CARDIA) cohort. Results: The mean Max dur was ≈7.5 s shorter per kilogram of fat mass in both men and women and independent of fat-free mass, height, race, television watching, physical activity, systolic blood pressure, lung function, and education. Fat mass modified the association of fat-free mass with the Max dur (2-way interaction P < 0.001), and the interaction was stronger in women than in men. In men in the lowest fat-mass quartile, the Max dur was 1.3 s longer per kilogram of fat-free mass and was 0.5 s shorter per kilogram of fat-free mass in the highest fat-mass quartile. In contrast, in women with the least fat mass, the Max dur was 2.7 s longer per kilogram of fat-free mass and was 2.8 s shorter per kilogram of fat-free mass in the highest fat-mass quartile. Conclusions: The Max dur was negatively related to fat mass. Fat-free mass in obese people contributed little to the treadmill performance potential as assessed by the Max dur, although the contribution of fat-free mass was positive in thinner people. © 2011 American Society for Nutrition.