We provide first evidence of the impact of over-education, among natives and immigrants, on firm-level productivity and wages. 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 outweighs the corresponding wage premium differential, we conclude 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).