This paper reports a study about the perceptions of the academic community, employers and civil servants regarding graduates' employability skills in East Africa. Specifically, it focuses on the mismatch between skills acquired in Higher Education (HE) and those in demand by employers, and explores factors influencing the situation. A mixed method approach was implemented including a survey and a set of focus groups. The questionnaire on employability skills was distributed among regional stakeholders attending the Open Day events organised by three East African HE Institutions. A Principal Components Analysis was applied for the categorisation of the most in-demand skills and the identification of four major workplace skill sets. To gain further insights into the stakeholders' perceptions of the graduate employability skills gap, 11 focus groups were organised at the same universities. The general results showed that employability skills were mostly perceived as insufficiently developed during the students' progress in their programs. The final results enabled a better understanding of the nuanced relationship between labour market valuation and graduates' acquisition of each skill set. It also allowed us to identify problems and barriers, and suggest possible solutions to overcome the shortcomings experienced by the sub-Saharan HE system.