Background: To address nutrition-related population mental health data gaps, we examined relationships among food insecurity, diet quality, and perceived mental health. Methods: Stratified and logistic regression analyses of respondents aged 19–70 years from the Canadian Community Health Survey, Cycle 2.2 were conducted ( n = 15,546). Measures included the Household Food Security Survey Module, diet quality (i.e., comparisons to the Dietary Reference Intakes, Healthy Eating Index), perceived mental health (poor versus good), sociodemographics, and smoking. Results: In this sample, 6.9% were food insecure and 4.5% reported poor mental health. Stratified analysis of food security and mental health status by age/gender found associations for poor diet quality, protein, fat, fibre, and several micronutrients ( p-values < 0.05); those who were food insecure tended to have higher suboptimal intakes ( p-values < 0.05). After adjustment for covariates, associations in relation to mental health emerged for food insecurity (OR = 1.60, 95% CI 1.45–1.71), poor diet quality (1.61, 95% CI 1.34–1.81), and suboptimal intakes of folate (OR = 1.58, 95% CI 1.17–1.90) and iron (OR = 1.45, 95% CI 1.23–1.88). Conclusions: Population approaches that improve food security and intakes of high quality diets may protect people from poor mental health.