Background: The prevalence of young people not adhering to the World Health Organization (WHO) physical activity guidelines is high, especially among students in vocational education and training, compared to fellow peers. Also, low levels of mental health have been found in this group, however, to a lesser degree than peers in general education. As positive mental health aspects have more generally been found to be associated with increased likelihood of physical activity in young people, this study examined the association between mental health and physical activity among Danish students in vocational education and training. Methods: Students in vocational education and training (N = 5277, mean age 24.3 years, range 15.8-64.0 years) responded to a national representative survey assessing four aspects of mental health (well-being, self-efficacy, self-esteem and life satisfaction) and physical activity. Physical activity was dichotomized as adherence to the WHO minimum guidelines or not. Logistic regression was used to examine if each mental health aspect was associated with physical activity in crude and adjusted models. Results: A positive dose-response association was found between all aspects of mental health and adherence to WHO physical activity guidelines. However, the association between self-esteem and physical activity was modified by gender, with a dose-response relationship found only among males. Conclusions: Higher levels of positive mental health were associated with better odds of achieving WHO physical activity guidelines in a dose-response-manner. Prospective studies are needed to further elucidate the causal relationship between mental health and physical activity. Future interventions must pay attention to differential gender effects.