The adoption of Competence-Based Education (CBE) in higher education has become a significant strategy towards aligning university programmes with labour market demands and enhancing graduate employability. The Open University of Tanzania (OUT), being the leading Open and Distance Learning (ODL) institution in the East African region, has been at the forefront of integrating CBE into its programmes. Nevertheless, challenges still remain, particularly in ensuring competence acquisition, practical training, and regulatory compliance. This study examined OUT’s institutional experience in embedding CBE in its academic programmes with the aim of identifying institutional achievements, challenges, and lessons for strengthening quality CBE delivery in ODL. A mixed-methods approach was employed, whereas quantitative data were collected using students' surveys and institutional records, while qualitative data were obtained from document reviews, semi-structured interviews with academic and QA staff, and focus group discussions with students. Quantitative data were analysed using descriptive statistics, whereas qualitative data were subjected to thematic analysis. The findings reveal that both students and staff widely support the implementation of CBE. Specifically, 93.3% of students agreed that CBE effectively prepares graduates for the labour market, while 78% expressed satisfaction with the University's QA processes, reflecting confidence in programme delivery and assessment standards. Nevertheless, access to practical training remained constrained, with only an average of 65.5% of students reporting opportunities for internships or industry placements. Qualitative findings further identified limited industry partnerships, financial constraints, and QA frameworks that are insufficiently adapted to the realities of ODL as key implementation challenges. The study concludes that in order to sustain CBE within ODL, there is a need to build up industry-academia partnerships, scale up digital simulations to supplement physical training and to align QA frameworks with the realities of distance education. Lessons from OUT provide practical strategies for policy makers, QA agencies and ODL institutions aiming to improve the credibility and relevance of CBE in the region and beyond.