The Horsemen are recently graduated adventurers from the Adventures & Missions Academy of the Defenders of the Alliance, a semi-independent military arm of the kingdom of Lordaeron.
Lordaeron has long been a fragmented country, with city states of the different Free Races all squabbling over the usual greed of land, gold, and power. It was not until demons and undead and all sorts of unspeakable horrors with large teeth and sharp appendages ravaged the lands through numerous arcane portals that the Free Races put aside their quarrels and banded together against the onslaught.
Thus was the Alliance formed, and with it, the Defenders. In what is later to be called the Scourge War, the Defenders fought valiantly and emerged victorious, though with countless lives lost and many cities and towns destroyed. The demons were driven back, the portals sealed.
Now, generations later, with the Scourge menace fading into the history books, the Alliance is on the verge of breaking apart as the Free Races once again vie for their own profit. The Defenders are only a shell of their former glory, surviving as an adventurer's guild who will undertake missions for anyone who can pay.
However, there are still a few members aware of the danger the break down of the Alliance represents, for shadows rouse in long forgotten lands where once the nefarious portals stood, and a threat perhaps greater than the Scourge stirs.