Higher education institutions are responsible for providing their graduates with relevant job skills that will allow them to compete in the labour market. With this in mind, the purpose of this study was to identify the factors associated with graduate unemployment in Ethiopia. The data were collected, analysed, and interpreted using a quantitative design. Using Cochran's sampling formula, 359 graduates from five regions were selected as the sources of primary data. Multinomial logistic regression was used to analyse the data because it is a good model for computing the interaction between more than two independent and dependent variables. Cronbach's alpha coefficient of 0.947 indicated that the instrument's reliability is adequate. The study revealed that the independent variables that correlate with graduates' unemployment are demographic characteristics, curriculum, institutional characteristics, graduate characteristics, and economic and labour market conditions. These findings imply that HEIs and governance bodies should reconsider the sector's policy and strategic directions in terms of graduates' employability output. As one of the major improvements, the study also recommends creating an enabling environment for employers to thrive, while higher education institutions adjust their curricula to meet the needs of employers.