Work-related stress is considered one of the biggest health and safety challenges among the member states of the European Union. A critical factor is recovery between periods of stress. The primary purpose of this study was to investigate whether a brief behaviorally oriented stress-recovery management intervention delivered in an individual setting could reduce stress symptoms among individuals with high levels of perceived stress. A single-subject experimental design with multiple baselines across three individuals was used. The results indicate, with at least moderate experimental control, a temporal relation between the start of the intervention and beneficial changes from baseline in continuous self-recordings of stress symptoms. The changes were maintained at 1-year and 5-year follow-up assessments. Also, self-reporting inventories measuring perceived stress, worry, anxiety, depression, burnout, type A behavior, unwinding and recuperation from work stress, and insomnia showed overall changes in beneficial directions at post-assessment, as well as the two follow-up assessments. The results indicate that a behaviorally oriented stress-recovery management intervention delivered in an individual setting can reduce stress symptoms in individuals with high levels of perceived stress. However, for firm conclusions to be drawn, further research is needed.