Graduate unemployment has increasingly been the topic of research interest as it grows in many countries. In many such contexts, the massification of higher education and the global economic recession of the late 2000s explain the challenge. The situation differs in South Africa. Graduate unemployment rates are low owing to the high demand for skilled labour. However, certain groups of graduates continue to struggle to find employment. While previous research has described which graduates are more vulnerable to unemployment, few studies have assessed the reasons for their struggle. We address this gap by presenting data from a mixed methods study, which included a sub-sample of unemployed graduates, on the barriers these graduates face. The findings show that lack of relevant work experience, limited information about an efficient job search, low social capital, and high costs of work-seeking create obstacles to securing work. We reiterate recommendations from prior research that calls for better integration of qualifications with practical work experience, but also contend that accessible work-seeker support can mitigate the negative effects of the identified barriers. Such investments are critical to ensuring that significant investments in post-secondary education and training on the part of both the state and the individual graduate are realised.