Graduates' education and its alignment with the first job are of key influence on graduates' career. It is argued that education-job fit affects work-related learning, which is important for recent graduates to cope with the demands of their new job. Theoretically, two (contradicting) processes have been put forward describing the relationship between education-job fit and work-related learning: Whereas the "complementing" hypothesis argues that work-related learning builds on existing competences, the "substituting" hypothesis assumes that work-related learning compensates in case of misalignment. These hypotheses were assessed by identifying latent fit profiles of recent graduates (N = 779) and comparing differences regarding work-related learning. Four distinct profiles were identified: full fit, horizontal fit, vertical fit, and full misfit. Results supported the complementing hypothesis, arguing that learning at work complements what was learned during higher education. Furthermore, this study demonstrated how fit profiles differently influence formal and informal learning activities.