Background: Certain foods might be more frequently eaten under stress or when higher levels of depressive symptoms are experienced. We examined whether poor nutritional habits are associated with stress and depressive symptoms and whether the relationships differ by country and gender in a sample from three European countries collected as part of a Cross National Student Health Survey. Methods: A cross-sectional survey was conducted among first-year students in Germany (N = 696), Poland (N = 489) and Bulgaria (N = 654). Self-administered questionnaires included a 12-item food frequency questionnaire, Cohen's Perceived Stress Scale, and a modified Beck Depression Index. Linear regression analyses were conducted for two outcomes, perceived stress and depressive symptoms. Results: Food consumption frequencies differed by country and gender, as did depressive symptoms and perceived stress. For male students, none of the food consumption groups were associated with perceived stress or depressive symptoms. In females, perceived stress was associated with more frequent consumption of sweets/fast foods and less frequent consumption of fruits/vegetables. Additionally, depressive symptoms were associated with less frequent consumption of fruits/vegetables and meat. Conclusion: Our data show consistent associations between unhealthy food consumption and depressive symptoms and perceived stress among female students from three European countries, but not among male students. This suggests that efforts to reduce depressive symptoms and stress among female students may also lead to the consumption of healthier foods and/or vice-versa.