This study examined three linked questions in the teaching of artificial intelligence (AI) in Ugandan higher education: when in a student’s programme AI should be introduced, how it should be taught, and how institutions should respond to the competence dilemma that arises when the people expected to teach AI have not themselves been trained in it. The argument combined a conceptual analysis, drawing on constructive alignment, AI literacy and teacher knowledge frameworks, with a quantitative illustration. The study results indicated that the integration index averaged 50.9, and that self-rated competence (beta = 0.54, p < 0.001), STEM discipline, the use of AI tools in one’s own teaching, prior AI training and reliable computing resources were associated with greater integration, while years of teaching and academic-integrity concern were associated with less. Prior training (odds ratio = 4.34, p = 0.016) was the only significant predictor of support for early introduction. The diagnostic tests were satisfactory. The study concluded that competence was the binding constraint, and it recommended staged introduction, competence-building for lecturers before curriculum mandates, and assessment redesign.