The study investigates education-job mismatch in the graduate segment of the nation’s labour market, which has had to contend with increasing graduate unemployment in an environment that is inundated with frequent adverts for vacancies across graduate disciplines. Variance of relative unemployment and proportional index of unemployed and employed are used to explain the mismatch from 2012 to 2016. Mismatch is found to be low but increasing in the entire labour market. Aggregate unemployment rate was structurally dependent on unemployment rates among those without education and those who had secondary education while the rate was cyclically affected by unemployment rates in the ranks of those who had post-secondary education (graduates) and those who underwent less than primary education. The results of the proportional index analysis show that the graduates of Medical Sciences, Social Sciences/Business Studies and Engineering would not experience unemployment, while graduates with specialisations in Education, Law, Arts and Sciences were most likely to be unemployed in the Nigerian labour market. A number of reasons are offered to explain the plausibility of these results, while some solutions are put forward to address unemployment among graduates of the latter set of disciplines.