BACKGROUND: The aim of mentorship is to build the mentees capacity, enhance their skills and improve their ability to produce desired outcomes. However, the mentoring relationship is vulnerable to a number of challenges that may undermine its effectiveness and sustainability. We aimed to explore the experiences and perceptions of student and junior faculty mentees and senior faculty mentors at the Makerere University College of Health Sciences and identify the key factors defined by mentees and mentors as necessary for a successful mentorship program. METHODS: A qualitative design involving focus group discussions (FGDs) and key informant interviews (KII) was used. A total of eight KII and four FGDs were conducted, audio recorded and transcribed verbatim. Open coding of the transcripts was performed, and major themes were identified through multiple readings based on thematic analysis. RESULTS: Six key themes were shared by the mentees and mentors including: 1) defining the role of the mentor; 2) desired characteristics of a mentor and a mentoring relationship, with an emphasis on mutual trust and respect; 3) overlapping roles of mentors and supervisors; 4) issues with the process for identifying mentors, including the benefits and drawbacks of the mentee selecting mentor vs. being assigned a mentor; 5) current barriers to mentoring, including lack of knowledge about current program, lack of formal structure, uncertainly about who should initiate relationship, and unclear roles and expectations and 6) recommendations for the future development of mentoring programme, including the need for a formalized programme, and training adapted to the local context. CONCLUSIONS: The mentees and mentors described the role of the mentor and desired characteristics of mentors and a mentoring relationship similarly. Most concerns about mentoring occurred when current mentoring programmes and practices were not well aligned with these desired characteristics. Recommendations for future development of mentoring included greater formalization of mentoring with mentoring programmes based on shared expectations and adapted to the local context.