Introduction: Adequate sleep plays an integral role in the physical and mental health of individuals, while simultaneously influencing their cognitive and work performance. Having recognized this, the U.S. Army has focused efforts on improving soldiers’ healthy sleep behaviors. This study examines the extent to which mental health, alcohol use, and certain sleep hygiene behaviors predict sleep problems within an Army National Guard sample (N = 438). Materials and Methods: This manuscript is part of a larger study approved through the Minneapolis Veterans Affairs Medical Center Institutional Review Board. Mailed surveys were sent to Minnesota Army National Guard soldiers collecting data on sleep hygiene behaviors, mental health symptoms (post-traumatic stress disorder and depression), and alcohol use. Predictors of sleep problems were evaluated with ordinary least squares multiple linear regression analyses, regressing Insomnia Severity Index total scores on demographic variables, post-traumatic stress disorder (PTSD), depression, alcohol use, sleep hygiene factors (routine and consumption activity; both derived from exploratory factor analysis), and technology use (multiple device use and use before bed). Results: Overall, the majority of participants did not endorse high levels of sleep impairment, while 16.4% screened positive for moderate or even severe levels of clinical insomnia. Bivariate correlations demonstrated that sleep problems were correlated with PTSD symptoms (r = 0.41, p < 0.001), depression (r = 0.49, p < 0.001), Sleep Hygiene Routine (r = −0.34, p < 0.001), and more frequent use of multiple devices before bed (r = 0.15, p = 0.002). The overall regression model predicting sleep problems was significant (R2 = 0.35, adj R2 = 0.34, F[8,408] = 27.58, p < 0.001). Independent predictors of sleep problems included gender (B = 0.99, β = 0.09, t = 2.10, p = 0.036), PTSD (B = 0.89, β = 0.22, t = 4.86, p < 0.001), depression (B = 1.53, β = 0.20, t = 7.56, p < 0.001), and Sleep Hygiene Routine (B = −0.88, β = −0.23, t = −5.473, p < 0.001). Alcohol use, Sleep Hygiene Consumption, and technology use did not emerge as independent predictors. Conclusion: Although most soldiers denied sleep problems, a sizeable minority met screening criteria for clinical insomnia. Greater numbers of sleep-related complaints were related to psychological distress including depressive and PTSD symptoms, while adherence to a bedtime routine (Sleep Hygiene Routine) showed an inverse relationship. Alcohol use and sleep hygiene consumption activities were not predictive of sleep problems, suggesting that different sleep hygiene behaviors have differential relationships with sleep problems. Screening and intervention for specific sleep problems may be helpful even very early in Army National Guard service members’ careers. Particular focus may be needed for those showing signs of emotional distress, such as PTSD or depression. Future research examining the impact of individual sleep hygiene components is warranted.