BeorntheBear: It depends on what you mean by "have a story". The game manual provides background information and there will be story elements scattered throughout the dungeon, but most the story will be left open to you speculate, infer, deduce, or imagine. Like most dungeon crawls, I am certain you will find yourself immersed within the game experience and finish the game thirsty for more information about the dungeon and the world itself.
One question I have is will it have NPCs or side quests. Or at least levels where there's more then just random puzzle filled hallways. Since I recall Ultima Underworld and older Might and Magic titles did. Whilst Legend of Grimrock isn't directly influenced by these titles as much as games like Eye of the Beholder, but it would be nice to know.
