Fatigue is common and persistent in stroke survivors, yet it is not known how mobility deficits, fitness, or other factors, such as social support, relate to fatigue severity, or whether subjective fatigue contributes to reduced ambulatory activity. The severity of fatigue in a sample of 53 community-dwelling subjects with chronic hemiparetic stroke was examined, and relationships among fatigue and mobility deficit severity, cardiovascular-metabolic fitness, ambulatory activity, social support, and self-efficacy for falls were identified. Measures included the Fatigue Severity Scale, timed 10-meter walks, the Berg Balance Scale, submaximal and peak VO2, total daily step activity derived from microprocessor-linked Step Activity Monitors, the Medical Outcomes Study Social Support Survey, and the Falls Efficacy Scale. Forty-six percent of the sample had severe fatigue. Fatigue showed no relationship to ambulatory activity. Fatigue severity was associated with the Berg Balance Scale (p > .01) and falls efficacy (p > .01), but not with cardiovascular fitness variables. Patients with elevated fatigue severity scores had lower social support (p > .05) and poorer falls efficacy scores (p > .05) than patients reporting less fatigue. Only falls efficacy was predictive of fatigue severity (r2 = 0.216, p > .01). Further studies are needed to evaluate whether rehabilitation strategies that include not only fitness and mobility interventions, but also social/behavioral and self-efficacy components, are associated with reduced fatigue and increased ambulation.