BACKGROUND: Partial unweighted treadmill training is a potentially effective modality for improving fitness and function in frail elders. We tested the feasibility of partial unweighted treadmill training in older, mobility-impaired veterans. METHODS: Eight mobility-impaired elders participated in partial unweighted treadmill training three times/week for twelve weeks. Outcome measures included gait speed, performance-oriented mobility assessment (POMA), eight foot up and go, and the SF-36 physical functioning short form. RESULTS: There was significant improvement in treadmill walking time (+8.5 minutes; P < 0.001), treadmill walking speed (+0.14 meters/second; P = 0.02), and percent of body weight support (-2.2%; P = 0.02). Changes in physical performance included usual gait speed (+0.12 meters/second; P = 0.001), rapid gait speed (+0.13 meters/second; P = 0.01), POMA (+2.4 summary score; P < 0.001), and eight foot up and go (-1.2 seconds; P = 0.05). CONCLUSIONS: Partial unweighted treadmill training is feasible in mobility-impaired elders. Improvements in treadmill training capacity resulted in clinically meaningful improvements in fitness levels and improved mobility.