A group called Mind.In.A.Box has done something like this... although on a slightly larger scale as their first 3 albums have a sci-fi/noir story woven through them which makes the music all the more compelling.

It can be found on spotify with the order being 'Lost Alone', "Dreamweb' and finally 'Crossroads'

Detachable Penis - King Missile

Seconding Blind Guardian; pretty much every single one of their songs tell a story. Many of them tell others' stories though, if that's a problem (Wheel of Time, Lord of the Rings, the entire album Nightfall in Middle Earth, etc.)