Every teacher aspires to create the ideal lesson! You want to convey the knowledge and skills in the best possible way while also keeping learners motivated. In our design case, we focus on the complex skill of collaborative problem-solving (CPS). In today's complex world, the acquisition of CPS competencies is considered an important learning goal in education. However, there is limited knowledge on how to teach and assess CPS competencies. In addition to tackling these challenges, we search for new ways of interactive storytelling to implement in the learning materials. Our main design challenge was how to design a learning experience that encourages CPS. To address these challenges, we started in 2020 the project titled Supporting TEamwork in AMbient learning Spaces (STEAMS). In this project, we designed the EDUbox Teamwork, a four-hour learning activity for children between the ages of 10 to 14. In this paper, we describe the iterative process of designing the materials to learn about CPS (i.e., CPS as a learning goal) by doing CPS (i.e., CPS as a method), enhanced by interactive storytelling, for which the design-based research approach was used. The design team consisted of a diverse group of educational researchers, computer scientists, instructional graphical designers, digital storytellers, and teachers. Given the strong collaboration between a research group specialized in computer-supported collaborative learning and specialists in digital storytelling, our design case incorporated insights from both parties. The learning activity was piloted both in in-vivo and in-vitro contexts in collaboration with at least 400 students.