This paper examines the relationship between immigration and over-education, taking advantage of access to rich matched employer-employee data for the Belgian private sector for the period 1999-2010. Covering more than 1.2 million workers, the data enable the authors to: i) measure over-education with higher precision, ii) examine the heterogeneous effects of detailed countries of birth, and iii) test the role of key moderating factors. More precisely, this paper is not only the first to investigate the effect of citizenship acquisition and workers' tenure on the nexus between immigration and over-education, but also one of the few to study the moderating roles of gender and education for detailed categories of immigrants. With ordered probit estimates, the authors highlight that immigrant workers are much more likely to be over-educated than their native counterparts, especially when the former originate from the Maghreb or Asia. Over-education also appears to be particularly critical among higher-educated immigrants. Gender-based differences in immigrants' penalties, in contrast, are found to be quite modest overall. Results further show that tenure has a strong moderating effect on the likelihood for immigrants born in developing countries to be over-educated and that citizenship acquisition is also associated with substantially improved job matches.