Background and Purpose— Prospective data on the association between cardiorespiratory fitness (CRF) and stroke are largely limited to studies in men or do not separately examine risks for fatal and nonfatal stroke. This study examined the association between CRF and fatal and nonfatal stroke in a large cohort of asymptomatic women and men.Methods— A total of 46 405 men and 15 282 women without known myocardial infarction or stroke at baseline completed a maximal treadmill exercise test between 1970 and 2001. CRF was grouped as quartiles of the sex-specific distribution of maximal metabolic equivalents achieved. Mortality follow-up was through December 31, 2003, using the National Death Index. Nonfatal stroke, defined as physician-diagnosed stroke, was ascertained from surveys during 1982 to 2004. Cox regression models quantified the pattern and magnitude of association between CRF and stroke.Results— There were 692 strokes during 813 944 man-years of exposure and 171 strokes during 248 902 woman-years of exposure. Significant inverse associations between CRF and age-adjusted fatal, nonfatal, and total stroke rates were observed for women and men (Ptrend≤0.05 each). After adjusting for several cardiovascular disease risk factors, the inverse association between CRF and each stroke outcome remained significant (Ptrend<0.05 each) in men. In women, the multivariable-adjusted relationship between CRF and nonfatal and total stroke remained significant (Ptrend≤0.01 each), but not between CRF and fatal stroke (Ptrend=0.18). A CRF threshold of 7 to 8 maximal metabolic equivalents was associated with a substantially reduced rate of total stroke in both men and women.Conclusions— These findings suggest that CRF is an independent determinant of stroke incidence in initially asymptomatic and cardiovascular disease-free adults, and the strength and pattern of the association is similar for men and women.