Objective: To investigate the relationship between physical fitness and work integration following stroke. Design: Single-group study, measurement of physical fitness pre and post physical training, measurement of employment status in a follow-up assessment 2 to 36 months after rehabilitation. Setting: Interdisciplinary outpatient rehabilitation program. Participants: 58 stroke survivors (62% male, mean age at program start 46.7 years, mean time since stroke 1.1 years) who were consecutively referred to the program. Intervention: 1½ hours of intensive training of cardiorespiratory fitness and muscle strength 1–3 times weekly as part of the 3-month program. Measures: Physical fitness was measured with a modified Harvard Step Test, the Åstrand Cycling Test, and walking/running speed. The type of participants' employment as well as the amount of working hours was registered. Results: Good physical fitness as measured by the Harvard Step test, but not the Åstrand Cycling Test and walking/running speed, was related to return to competitive, full-time employment. Test results from training tended to predict work reintegration better than test results from training start. Improvement of physical fitness as measured by the Harvard Step Test was also related to follow-up employment. Conclusions: The results imply a relationship between physical fitness and work integration following stroke and should be confirmed with a randomised controlled study design.