Here's an example of a storyline:
After the creation of Azeroth and the five Dragonflights, there was also a small planet created called the X (insert cool name here). The five Dragonflights were asked to destroy X, as it was an impurity to the Azeroth, the creation of the Titans. Upon entering X, a sixth Dragonflight was created by the Titans, the Night Dragons. They were also sent to X to aid the other Dragonflights in their mission. X was unstable at the arrival of the Dragons, and many creatures (the creeps you fight) were risen from the earth. The Dragonflights used their powers of creation to destroy the creatures and claim their essences to empower them (the dragon eggs). When the final creature (end boss), was risen, the Dragonflights combined their powers to slay it. The portal, which empowered the creatures to rise from the earth, still remained. The Sixth Dragonflight, the Night Dragons, sacrificed themselves to seal the portal shut, put the other Dragonflights to safety, and clear X entirely from the world. The five remaining Dragonflights still have the powers they claimed from the creatures from X and now use it on Azeroth.
EDIT: To fit the lore, the creeps spawned (instead of footmen, ghouls etc. in the current map), should be changed to the creatures from X. I can also help designing the stats and abilities of those units, and test future versions of the map.