Little research in Interactive Digital Storytelling (IDS) has been given to writing stories that convey a set of Learning Objectives (LOs). This is particularly important for educational IDS games. In this paper, we propose the STAR framework for formalizing the design of IDS stories for educational interventions. The story is designed as a set of red-herrings and clue puzzle in which the LOs are integrated. We present one of the three IDSes we designed based on this framework; we use one as a case study and present its evaluation. A study was undertaken to evaluate the game effectiveness in conveying the educational message. This study performed with 145 players shows that the players’ knowledge improved as a result of playing the game and that the change was statistically significant.