Diet quality, physical activity, alcohol use, smoking, sleep and sitting-time are behaviors known to influence health. The aims of this study were to identify how these behaviors co-occur to form distinct health-behavior patterns, and to investigate the relationship between these patterns, and mental and self-rated health. Members of the Australian 10,000 Steps project were invited to participate in an online survey in November–December 2011. The participants self-reported demographic and behavioral characteristics (fruit and vegetable intake, fast food, soft drink and alcohol consumption, smoking, physical activity, sitting-time and sleep), frequency of mental distress and self-rated health. Latent Class Analysis was used to identify health-behavior patterns. Latent class regression was used to examine relationships between behavior patterns, mental and self-rated health, and socio-demographic and economic factors. Data were analyzed in October 2017. Complete datasets were obtained from 10,638 participants. Four latent classes were identified, characterized by ‘Low-Risk Behavior’, ‘Poor Sleep, Low-Risk Daytime Behavior’, 'sound Sleep, High-Risk Daytime Behavior’ and ‘High-Risk Behavior’. The latter two classes, both characterized by high-risk daytime behaviors, were associated with poor self-rated health. Participants in classes with high-risk daytime behaviors were more likely to be younger, non-partnered, non-university educated, from lower income households and work longer hours. Classes characterized by poor sleep quality were associated with higher frequency of mental distress. Findings suggest that experiencing poor sleep is partly independent of daytime behaviors, demographic and socioeconomic factors, but has a strong association with mental health.