The increasing use and application of Artificial Intelligence (AI) across various sectors in society, combined with the growing adoption of emerging technologies, emphasizes the urgent necessity to develop digital competencies in K-12 education, encompassing both digital literacy and AI literacy. Computational thinking (CT) has been recently incorporated into the educational curricula of several countries as it is regarded as an effective approach to improving problem-solving and programming skills. AI literacy, however, has only recently started to gain attention and make its way into K-12 teaching. Few studies to date have investigated to what extent having a technical understanding of AI methods and techniques can contribute to actual AI literacy thus finding effective ways to integrate this knowledge into policy and curricula. To address this problem and contribute with empirical insights, we designed and conducted a study identifying the challenges and the opportunities teaching basic concepts of AI to a class of middle school students. During a workshop series, an entire class of 8th graders engaged in hands-on activities related to CT and AI with a particular focus on machine learning. We identify a lack of prerequisite skills that impact students’ ability to engage in contextual AI-related activities due, at least partly, to poor programming skills. This, in turn, seems detrimental to gaining transferable skills in machine learning which are important given the interdisciplinary nature and broad application of these AI methods. We identify CT and programming as prerequisite skills necessary to achieve a deeper understanding of AI technology and its implications for individuals and society.