Interactive media offer outstanding possibilities for the presentation and preservation of tangible and intangible cultural heritage. The users are transferred to the past where they can experience historical events, see original appearances of cultural monuments, and learn about customs, skills, and traditions of people long gone and forgotten. Digital cultural heritage applications aim to introduce them to historical topics in an educational and entertaining way and create a so-called “edutainment” factor. This is easiest achieved through gameplay elements. In this chapter, we will show how to obtain a high level of immersion and edutainment through the combination of interactive digital storytelling and gameplays in selected VR applications for cultural heritage. We will explain how this methodology helps in overcoming the narrative paradox problem. We consider gamification a great tool to improve learning and user experience in any topic, not just cultural heritage, and recommend the application of the presented methods to other education fields.