The increased integration of Artificial Intelligence (AI) in society encourages the educational field to explore its potential to enhance teaching and learning. To achieve this, an AI literacy program for pre-service teachers plays a crucial role and determines the effective and ethical implementation of these technologies in early education. This study investigates pre-service teachers' perceptions, attitudes, and perceived challenges regarding the integration of AI literacy within kindergarten and primary school settings. Employing a qualitative approach, data were gathered from 51 university students following a training module at the University of Verona. Analysis involved inductive content analysis of open-ended reflections. Respondents identified a lack of basic skills and, indeed, the key role of AI literacy training path for an effective integration of AI in classes. Besides this, they highlighted the need to develop a critical awareness that allows them to promote a responsible and critical use of this tool. Finally, in the form of guidelines, they highlighted principles and practices that they consider essential for integrating AI into primary and preschool settings. In conclusion, the study shows pre-service teachers are developing a human-centred approach to AI. However, transitioning these "directional hypotheses" into classroom reality requires institutional support that empowers teachers as active agents of curricular innovation.