Background: Depression and anxiety are common mental health concerns worldwide. Broad-spectrum multi-vitamin/mineral approaches have been found to alleviate a number of psychiatric symptoms. We investigated the effects of a nutrient intervention program, which includes optimizing vitamin D levels, on depression and anxiety outcomes from community-based program. Methods: We evaluated self-reported health measures of depression and anxiety collected as part of a community-based program focused on optimizing overall health through nutritional supplementation, education and lifestyle advice. Results: Data were collected from 16,020 participants, with measures including European Quality of Life Five Dimensions (EQ-5D) and Targeted Symptoms List (TSL) providing self-reported depression and anxiety. More than 56% of participants were identified as having elevated levels of depression and anxiety at baseline as reported on the EQ-5D. After one year in the program, 49.2% (n = 7878) of participants who reported any level of depression or anxiety at baseline reported improvement at follow-up. Of those who reported severe/extreme depression at baseline (n = 829), 97.2% reported improvement after one year. Regression analyses revealed a significant association of improvement in depression and anxiety with higher vitamin D status (>100 nmol/L) and more strenuous physical activity. Conclusion: Overall, people from the general population who suffer from mood and anxiety problems may benefit from improved nutritional status achieved with nutritional supplements.