Increasingly, among international organizations concerned with unemployment rates and industry demands, there is an emphasis on the need to improve graduates' employability skills and the transparency of mechanisms for their recognition. This research presents the Employability Skills Micro-credentialing (ESMC) methodology, designed under the EPICA Horizon 2020 (H2020) project and tested at three East African universities, and shows how it fosters pedagogical innovation and promotes employability skills integration and visibility. The methodology, supported by a competency-based ePortfolio and a digital micro-credentialing system, was evaluated using a mixed-method design, combining descriptive statistics and qualitative content analysis to capture complementary stakeholder perspectives. The study involved the participation of 13 lecturers, 169 students, and 24 employers. The results indicate that the ESMC methodology is a promising approach for supporting students in their transition from academia to the workplace. The implementation of the methodology and the involvement of employers entails rethinking educational practices and academic curricula to embed employability skills. It enables all actors to broaden their understanding of the relationship between higher education and the business sector and to sustain visibility, transparency, and reliability of the recognition process. These findings indicate that there are favourable conditions in the region for the adoption of the approach, which is a meaningful solution for the stakeholder community to address the skills gap.