Humans use stories to explain natural processes, to explore alternatives, to resolve issues, and to imagine different possibilities and futures. Stories are a fundamental way people connect to their natural surroundings. But are some stories better for this than others? This study uses an experimental design to explore the impact of three types of stories on perceptions of natural landscapes. Using photographs of four diverse landscapes and four story conditions (no story, a story with a scientific focus, a European human story, and an Indigenous creation story), 733 respondents were exposed to one of 16 conditions and asked to rate landscape perception and preference and intention to visit. Stories, particularly those with a scientific or Indigenous creation focus, enhanced the appeal of the landscapes. Key elements of the stories that may have enhanced respondents' perceptions of, preferences for, and intentions to visit a particular landscape are proposed.