Abstract Background. Lifestyle changes are advocated as a first line of treatment for dyslipidemia. However, few studies have directly compared various combinations of diets and exercise. Methods. In a randomized controlled pilot study, we compared the standard lifestyle recommendations (NCEP step I diet with regular exercise) and more intense interventions including the NCEP step I diet with a supervised aerobic exercise program and the step II diet with and without a supervised aerobic exercise program. We measured risk factors, dietary intake, time on treadmill, and health-related quality of life at baseline and after 3 months. Results. Out of 198 eligible subjects, 47 (24%) were willing to participate and 41 completed the study. No significant change were observed with standard lifestyle recommendations. In contrast, participants in the more intense interventions lost weight (−1.7 to −3.7 kg) and reduced their total cholesterol (−4% to −6%), low-density lipoprotein cholesterol (−6%), and systolic blood pressure (−7.3 to −8.8 mmHg). Participants in the exercise program significantly increased their exercise capacity (1.6 to 1.9 METS). Overall, each 10% reduction in body weight was associated with a 7.6% reduction in low-density lipoprotein cholesterol. Conclusion. Standard lifestyle recommendations had little effect on blood lipid levels but more intense lifestyle interventions may be effective at improving blood lipids, other risk factors, and quality of life.