For more than 2 years, Scratch programming has been taught in Taiwanese elementary schools. However, past studies have shown that it is difficult to find appropriate learning methods or tools to boost students' Scratch programming performance. This inability to readily identify tutoring tools has become one of the primary challenges addressed in Scratch programming studies. To cope with this problem, we propose an innovative approach, which combines an Annotation-based Scratch Programming (ASP) tool with the problem-solving-based teaching approach in Scratch programming pedagogy. The ASP tool was developed to enable students to create, review and share Scratch programming and homework annotations. In a quasi-experimental study, we have evaluated Scratch programming pedagogy at a North Taiwanese elementary school to investigate the effects of instructional-tools-supported programming instructional modes on Scratch programming performance. The experimental results show that students who received ASP tool support in conjunction with a problem-solving-based teaching approach performed significantly better than the other groups. Based on our findings, the innovative approach was believed to play an important role in improving the learning patterns of younger pupils. Therefore, we suggest that teachers consider incorporating the innovative method into their teaching environments in order to boost students' learning achievements in the area of Scratch programming and the subsequent learning process.