Teaching artificial intelligence (AI) is an emerging challenge in global school education. There are considerable barriers to overcome, including the existing practices of technology education and teachers’ knowledge of AI. Research evidence shows that studying teachers’ experiences can be beneficial in informing how appropriate design in teaching sustainable AI should evolve. Design frames characterize teachers’ design reasoning and can substantially influence their AI lesson design considerations. This study examined 18 experienced teachers’ perceptions of teaching AI and identified effective designs to support AI instruction. Data collection methods involved semi-structured interviews, action study, classroom observation, and post-lesson discussions with the purpose of analyzing the teachers’ perceptions of teaching AI. Grounded theory was employed to detail how teachers understand the pedagogical challenges of teaching AI and the emerging pedagogical solutions from their perspectives. Results reveal that effective AI instructional design should encompass five important components: (1) obstacles to and facilitators of participation in teaching AI, (2) interactive design thinking processes, (3) teachers’ knowledge of teaching AI, (4) orienteering AI knowledge for social good, and (5) the holistic understanding of teaching AI. The implications for future teacher AI professional development activities are proposed.