This paper proposes a method to effectively utilize multimedia databases created and indexed by a metadata schema designed specifically for AR applications used at cultural heritage sites. We attempt to do so by incorporating storytelling principles that employ video data for the purpose of providing useful and meaningful guidance at Changdeokgung Palace, a UNESCO World Heritage Site that consists of multiple PoIs. We designed a themed narrative that embeds video data related to the PoIs, creating a guide route that connects each PoI in a fixed order. An extensive between-group user evaluation comparing a search-based AR experience and the proposed narrative-based one was conducted to test and prove the validity and effectiveness of our approach. Our results show that storytelling is indeed a significantly powerful tool to enhance the level of immersion users experience through video data in an AR environment at cultural heritage sites.