Background: University students have high levels of poor sleep quality (SQ) and mental health, and low adherence to healthy nutrition and physical activity (PA). Objective: This study examined what clusters of self-care behaviors (SCB) were associated with SQ and mental health in Australian university students. Method: 355 Australian university students, ranging in age from 18 to 24 years (M = 20, SD = 1.5, 286 females) completed surveys relating to fruit and vegetable consumption, alcohol binge behavior, PA, mental health measured by the Depression Anxiety Stress Scales 21, and SQ measured by the Pittsburgh SQ Index (PSQI). Fruit and vegetable consumption, alcohol binge behavior, and PA were assessed according to current Australian guidelines. Results: Almost two thirds of participants (62.0%) met the criteria for poor SQ. Good SQ was significantly associated with meeting PA guideline levels (r b = .14) and inversely associated with higher levels of depression (r pb = −.34), anxiety (r pb = −.36), and stress levels (r pb = −.42). Four distinct SCB and mental health risk clusters were created. The “healthiest SCB” cluster had 1.6 times better SQ than the average. This cluster had higher levels of moderate and vigorous PA, higher levels of fruit consumption, and less binge drinking, the least sedentary behavior, and the lowest levels of depression, anxiety, and stress compared to the other clusters. Conclusion: This research corroborates with previous literature on the importance of regular vigorous PA as a lifestyle intervention to facilitate better sleep outcomes and improved mental health outcomes in university students.