I would distinguish between stories and narratives. The story is always something imposed upon you, while a narrative can be quite abstract and emergent - like, going through the levels in Dungeon Master looking for keys to locked doors and stuff does create a narrative, but there's very little story to it. Myst and the better Myst-likes are quite similar in structure - there is an extensive backstory and an end goal, but nothing much happens in the game itself apart from the player exploring the world and solving puzzles.
A well-constructed narrative is necessary to structure the player's experience, providing long-, short- and medium-term goals - but all of this can be communicated through exploration and environment, none of it requires characters, dialogs or stories. And Adventures are actually positioned best to provide such emergent environmental narratives because more and less complex puzzles automatically create longer and shorter term goals for the player.