The benefits of utilizing storytelling at tourism destinations have been widely discussed, yet despite recent advances, it remains unclear which story elements comprise a good destination story and what the most effective modes are for story presentation. The current study examines the influence of story elements and presentation modes on memory performance and visit intention to the destination described in the story. The results show that the story elements of authentic cues and positive emotion increased the subjects’ perceived memory of the story and their visit intention. Moreover, subjects exposed to an audio-visual presentation mode demonstrated better perceived memory recall and higher visit intention. In today’s fiercely competitive climate, many tourism destinations use stories to attract visitors, and these findings can provide insights for destination managers and marketers to help them better utilize storytelling at their destinations.