Integrating narrative elements into a game is a key element in de-signing an immersive experience. Narrative has been hypothesized to improve engagement, motivation, and learning within educational environments. While empirical results have been produced to show that narrative enhances engagement and motivation, its effects on learning were shown to either be insignificant or negative. We, there-fore, aim to address the question of how to integrate narrative in a game to improve learning. We address this through the design of May’s Journey, an educational game that teaches basic programming concepts where a story is integrated. The game design seamlessly integrates learning goals, core mechanic and narrative elements. In this paper, we discuss the game design as well as a study we con-ducted to compare two game versions, one with rich narrative and the other with light narrative. Results demonstrate that participants who interacted with the rich narrative version had fewer programming errors and increased engagement within the game. We present our contributions in the form of educational design principles for narrative integration supported by our study and results.