This study contributes to the employability skills debate by investigating how students’ self-perceived 21st century skills relate to the self-perceived fit between their higher education curriculum and their future labor market for a sustainable entry to this labor market. Survey data from 4670 fourth-year students over a period of four years were analyzed. Furthermore, out of this group, 83 students were monitored longitudinally over their full educational student careers. Results showed a positive relationship between students’ self-perceived 21st century skills and their self-perceived “education-future labor market fit”. Among more recent cohorts, a significant improvement in their self-perceived 21st century skills was found. Overall, this study indicated that in order to deliver “employable” graduates, students need to be thoroughly trained in 21st century skills, and their development should be retained and expanded. This is one of the few studies that uses a vast amount of both cross-sectional and longitudinal data on skills and labor market perspectives among new graduates.