Exploring a rich matched employer-employee data set over the 1998-2012 period and a novel measure of educational mismatch, this study analyses the short and medium-term effects of over- and undereducation on the wages of newly hired workers. The data show that more than 50 percent of the employed in the private sector in Portugal experienced a job mismatch at the moment of being hired. According to the statistical measure based on the flows of newly hired workers, in the period under scrutiny overeducation is decreasing and undereducation is increasing, indicating that labour market demand is keeping pace with the rise in educational attainment of the Portuguese population. The results reveal that the wage differential between adequately matched workers and mismatched workers decreases considerably once worker and firm unobserved heterogeneity is taken into account. In fact, worker permanent heterogeneity explains two-thirds of the overducated wage penalty and three-fourths of the undereducated wage premium, indicating that the undereducated seem to correspond to a higher-ability group of employees, while the overeducated seem to correspond to a lower-ability group of workers. Heterogeneity in firm paying policies also play an important role in explaining the wage gap of newly hired mismatched workers. Finally, the results also indicate that the wages of individuals in the beginning of their labour market career are the most affected by a job mismatch.