Unexpectedly, the duration of first unemployment among first degree holders has quickly increased in Rwanda after considerable loss of the skilled labour during the war and Genocide perpetrated against Tutsi in 1994. The time it takes a higher education graduate to land a first employment is a key indicator for the evaluation of and optimal investment in higher education. A long-term first unemployment has negative psychosocial and economic consequences, and is an interplay of diversified factors. Yet, these factors have not been ascertained in Rwanda, whereas their knowledge is crucial for an efficient planning of higher education and employability of the graduates. This study aimed to fill in this knowledge gap for the period 1998–2009. We fitted a binary logistic regression model to data from the 2010 Employer and Graduate Survey (n = 1007) that was conducted by the National University of Rwanda. The results showed that the duration of first unemployment was significantly associated to the graduate’s age, job search method, acquired skills, further graduate studies, monthly salary and category of employing institution. The results suggest that the higher education sector should identify and fill skills gaps in the existing curricula or its delivery with reference to the labour market requirements.