As our society has advanced in the era of digital transformation, education has been transformed from knowledge-centered to competency-centered to solve future problems in the light of unpredictable changes and events in our lives. Programming education provides the basic knowledge needed, and fosters higher-order thinking skills in the process of generating and converging ideas to solve problems. However, in Korean elementary schools, it is mostly based on a lecture-based instructional design and focuses on knowledge delivery, which has limited the educational effects of programming. However, productive failure (PF) focuses on learning concepts in authentic problems, and lets the students generate different solutions and discuss them in an acceptable environment, with the result that they fail to solve the problem. Therefore, this study developed a PF-based educational program and tested it on sixth-grade students in a Korean elementary school. The results showed that the computational thinking (CT) and creative problem-solving (CPS) skills of the experimental group were significantly greater than those of the control group, with a medium effect size for CT and a high effect size for CPS skills. To generalize the results and increase the applicability, follow-up studies should expand the subject of the study, develop specific teaching guidelines for teachers, and invent various learning problems appropriate to the students’ level and different domains of learning.