Objectives: This study was to examine by gender the clustering patterns and correlates of healthy lifestyle clusters and the relationships between healthy lifestyle clusters and depressive symptoms in middle-aged and older adults. Methods: The observed/expected ratio of physical activity, smoking, and alcohol consumption were calculated to analyze clustering effects. The correlates of those healthy lifestyle clusters were evaluated using logistic regression models, and the relationship between those healthy lifestyle clusters and depressive symptoms was investigated using multiple regressions by gender. Results: Based on the guidelines this study adopted, we obtained three healthy lifestyle clusters: active healthy lifestyle; passive healthy lifestyle; and unhealthy lifestyle. All three clusters were found in men, but two in women, who did not have an unhealthy lifestyle cluster. High socio-economic status was positively related to healthy lifestyle clusters. Social participation and residence location (in men) and marital status (in women) were significant factors. Having an active or a passive healthy lifestyle was negatively associated with depressive symptoms in women, but such a relationship was not observed in men. Conclusions: The study findings imply that health promotion programs for middle-aged and older adults in Korea should be comprehensive and integrated, considering healthy lifestyle clusters and gender differences.