Background The effectiveness of a secondary prevention program for patients suffering from chronic heart failure (CHF) was evaluated. Purpose The program aimed at improving participants’ perceived health and actual physical symptoms. Insurants of a German health insurance company participated in a telephone counseling program with four modules focusing on dietary habits, physical activity, fluid intake, and medication compliance. Method Multilevel analyses were conducted to analyze changes in health related outcome variables over time in N = 259 participants who completed the program in about 6 months. Results The results showed an improvement of perceived health status, physical symptoms, and somatic impairment. Furthermore, differential change was found when comparing “finishers” compared to “non-finishers” of specific modules indicating specific module effects. Conclusion The results are auspicious and, if sustained, are expected to bring about long-term health benefits for our study’s participants. The program proved to be applicable and well accepted in the sample of older, severely impaired CHF patients and effective in changing perceived health.