Background: To investigate how social support relates to mental health problems for Belgian late adolescents and young adults 15–25 years of age. Additionally, we examine changes in mental health problems between 2008 and 2013 and investigate gender differences. Methods: Multivariate analysis of variance was used to investigate (1) psychological distress, (2) anxiety and (3) depression among 713 boys and 720 girls taken from two successive waves (2008 and 2013) of a representative sample of the Belgian population (Belgian Health Interview survey). Psychological distress was measured by the General Health Questionnaire, anxiety and depression by the Symptom Check-List-90-Revised. Results: Gender differences were found for psychological distress, anxiety and depression with girls reporting significantly higher scores than boys. Multivariate analysis of variance (MANOVA) revealed that adolescents who are dissatisfied with their social contacts and experience poor social support reported more psychological distress, anxiety and depression. In addition, young adult boys (20–25 years of age) were more likely to experience psychological distress when compared to late adolescent boys (15–19 years of age). Finally, the prevalence of anxiety and depression increased substantially between 2008 and 2013 for girls and to a lesser extent for boys. Conclusions: Especially girls and young people with poor social support experience mental health problems more frequently than boys and those with strong social support. Improving social support among young people may serve as a protective buffer to mental health problems.