We provide first evidence of the impact of over-education, among natives and immigrants, on firm-level productivity and wages. We use Belgian linked panel data and rely on the methodology from Hellerstein et al. (1999) to estimate ORU (over-, required, and under-education) equations aggregated at the firm level. Our results show that the over-education wage premium is higher for natives than for immigrants. However, since the differential in productivity gains associated with over-education between natives and immigrants outweighs the corresponding wage premium differential, we conclude – based on OLS and dynamic GMM-SYS estimates – that over-educated native workers are in fact underpaid to a greater extent than their over-educated immigrant counterparts. This conclusion is refined by sensitivity analyses, when testing the role of immigrants' background (e.g. region of birth, immigrant generation, age at arrival in the host country, tenure).