I had this idea when I was in the shower for a mashup of all the lores of the classic Blizzard games (Starcraft, Warcraft, and Diablo). The story I brainstormed is basically that the prime evils open a portal to hell in Northrend, allowing the demon armies to come out and set sail for Lordaeron, invading the world of Azeroth much the same way the orcs did in the first Warcraft game. Of course, the humans naturally fight back, and King Terenas sends Uther and Arthas, as well as the might of the Lordaeron army at their back, to face the prime evils in Northrend. While the battle is being waged, the Protoss appear (instead of Tyrael and the angels of the high heavens), sensing a psionic disturbance cause by the opening of the portal to hell in Northrend, and agree to join the alliance in defeating the prime evils. The alliance and the Protoss are successful in defeating the prime evils and close the portal to hell after a lengthy naval battle in the seas between Northrend and Lordaeron and an even lengthier land battle on the continent of Northrend itself. The Protoss decide to stay on the world of Azeroth to study the demons and the magic they used to get to Azeroth. They set up two major cities in Lordaeron. A civilian and research center named Qel-Shkshk, near Quel-Thalas, and Androlyn, a military center near Khaz Modan (These were names I thought of off the top of my head, if anybody has cooler sounding names, they can switch them out.). The Protoss begin trading with the Dwarves and Gnomes. The Dwarves, with their affinity for gunpowder and ballistics, are fascinated by the Protoss' photon technology, and end up creating their own Dwarf-themed photon cannons and photon blunderbusses and shotguns. The Gnomes, on the other hand, are in love with Protoss cybernetics and end up inventing Gnomish dragoon-tanks and psi-grenades that function like EMPs where when they explode they release psionic energy in the form of lightning, much like how a high templar can cast psi-storm in Starcraft. Dwarven technology looks like Protoss technology with medieval and gothic aesthetics and Gnomish technology looks similar to the weapons used in World Wars I and II. The Humans of Azeroth are the only ones not interested in the Protoss' gadgets, and during a meeting of all the races' leaders, a plan to colonize Azeroth slips from one of the representatives of the Protoss race, causing outrage among King Terenas and his Human advisors. The Dwarves and Gnomes, however, are less interested in politics than they are in continuing to advance their technology with the help of the Protoss. The Protoss end up invading Quel-Thalas in an attempt to find Terrazine, and the High Elves come to king Terenas for help. So the human armies of Lordaeron declare war on the Protoss, and the Elves begin creating enchanted weapons and armor to better help the humans defeat the Protoss by leveling the playing field in terms of implements of war. The Dwarves and Gnomes are outraged by the Humans attacking the Protoss and a civil war erupts. Eventually, the war between the Gnomes, Dwarves, and Humans results in a stalemate, and peace talks begin. The Humans convince the Dwarves and Gnomes that the Protoss have ulterior motives (much like how the UED tries to take over the Koprulu sector in Starcraft: Brood War) and convinces them to help the armies of Lordaeron to lay siege to the cities of Qel-Shkshk and Androlyn in hopes that the aggression will cause the Protoss to retreat back to the stars. An all out war erupts in Northern Lordaeron. The Protoss have legendary starships, so Dwarven Gryphon riders and Gnomish flying machines are in high demand for taking out the Protoss' massive fleet. There's also a cameo by the red, bronze, and blue Dragonflights fighting the Protoss because they believe that the Protoss' presence on Azeroth is upsetting the natural balance of the world, so the Protoss fleet is destroyed by the joint efforts of the Dwarves, Gnomes and Dragons. Then a land assault on the cities can begin, with the Dwarves, Gnomes, Elves, and Humans all battling against the Protoss armies. The alliance is able to destroy the Protoss cities and cause the majority of the Protoss to retreat. The remainder that stay as prisoners of war and harmless scholars form a new city named Terenasubad in honor of the might of King Terenas and his bravery in standing against the Protoss.
While the battle against the prime evils is raging in Northrend, the lesser evils set sail and land in Kalimdor (much like how the Vikings split up and discovered America and Russia separately). So there's a side story that evolves where the Night Elves must defeat the lesser evils with the help of the spirits of Kalimdor, like Cenarius. They are able to defeat them, but the events are so far removed from the main wars in Lordaeron that there are no Human scholars in Kalimdor at the time of the battles to document them to take back to the historians of Lordaeron, so it's essentially a moot point just for the sake of a spin-off of the main story.
In part 2, as the Protoss return to Aiur, they sense the prime evils are still at work, but this time influencing the orcs of Draenor. The prime evils are planning a second invasion of Azeroth using the orcs as pawns in their conquest. So the Protoss must ally with the Draenei, who would otherwise be defeated by the fel orcs without assistance and they're able to defeat the orc leaders. The Protoss realize that if they destroy the soul stones of the prime evils, they cannot be resurrected, so they proceed to assault the last bastions of demonic power in Draenor in an attempt to rid the universe of the prime evils for good. Much like the Quincies destroying the souls of Hollows from the anime Bleach, they are able to successfully destroy the soul stones and leave Draenor in the hands of the Draenei, and return to Aiur before the events of the first Starcraft game take place.
While the battle against the prime evils is raging in Northrend, the lesser evils set sail and land in Kalimdor (much like how the Vikings split up and discovered America and Russia separately). So there's a side story that evolves where the Night Elves must defeat the lesser evils with the help of the spirits of Kalimdor, like Cenarius. They are able to defeat them, but the events are so far removed from the main wars in Lordaeron that there are no Human scholars in Kalimdor at the time of the battles to document them to take back to the historians of Lordaeron, so it's essentially a moot point just for the sake of a spin-off of the main story.
In part 2, as the Protoss return to Aiur, they sense the prime evils are still at work, but this time influencing the orcs of Draenor. The prime evils are planning a second invasion of Azeroth using the orcs as pawns in their conquest. So the Protoss must ally with the Draenei, who would otherwise be defeated by the fel orcs without assistance and they're able to defeat the orc leaders. The Protoss realize that if they destroy the soul stones of the prime evils, they cannot be resurrected, so they proceed to assault the last bastions of demonic power in Draenor in an attempt to rid the universe of the prime evils for good. Much like the Quincies destroying the souls of Hollows from the anime Bleach, they are able to successfully destroy the soul stones and leave Draenor in the hands of the Draenei, and return to Aiur before the events of the first Starcraft game take place.