While there's plenty of great bands that create stories with their music, I'mma break out the big guns and mention Rush. They're perfect for this sort of thing, considering almost all their songs are either contained stories within themselves or even stories that span multiple albums.
Just one of the more obvious examples from them:
Just one of the more obvious examples from them: