Of course, Gul'dan didn't start off killing people and raising them from the dead or making two headed ogres. No, like all evil maniac geniuses, he started off as a baby and no matter how evil a baby is, the lack of motor control, small size, and tendency to soil oneself tends to inhibit making pacts with arch-fiends. For years, Gul'dan was just an ambitious but talented shaman serving under Ner'zhul. elder shaman of the Shadowmoon clan. It's possible they got along because Gul'dan, like Ner'zhul, hungered for power. It's possible they got along because they both have apostrophes in the middle of their names. At any rate, get along they did - when Ner'zhul started receiving visitations from a being who purported to be an ancient ancestor, the so-called 'beautiful one', Gul'dan had no problem supporting his campaign of war against the draenei. When Ner'zhul started to worry about the ancestors and the elementals refusing to aid the orcs in their war, Gul'dan had no problem following his master, spying on his meeting with the spirits, and discovering that the 'beautiful one' had lied to the orcs. And when Ner'zhul made to go reveal the truth to his people, Gul'dan had no problem going to Kil'jaeden and making a deal.
Power for service and loyalty. The power Ner'zhul wouldn't wield, Gul'dan would.
If you've been to Shadowmoon Valley, you've probably seen some of Gul'dan's handiwork. Not happy with betraying his teacher, forcing him into a toothless role as Elder Shaman without spirits to answer his call, determined to demonstrate just how powerful his deal with Kil'jaeden had made him. he chose to read from the Cipher of Damnation and literally tore Draenor away from its connection to the elemental spirits. The angered elementals still run amok there, and the Hand of Gul'dan stands as mute reminder of his power and his hubris. Gul'dan then attacked the Draenei at the Temple of Karabor and, conquering them, moved his Shadowmoon Clan into the place, renaming it the Black Temple.
And this was just his warm-up act. The slaughter of the draenei and the inducement of the orc communion with the Blood of Mannoroth was just to prove himself to Kil'jaeden. Having appeased the demonlord (who, after all, had been hunting the draenei for millennia) Gul'dan then began entrenching his position as head of the Horde by creating the Stormreaver clan and working his Shadow Council into positions of power throughout their society. For while Gul'dan was willing to do Kil'jaeden's dirty work, he wasn't content with mere temporal power, demonic magic or even near total genocide.
Gul'dan wanted to be a god. I know, I know, you all saw that coming. But Gul'dan, predictable or not, hungered for power on a scale even Kil'jaeden underestimated. But Sargeras understood that there was absolutely nothing Gul'dan wouldn't do for power. After the dark titan moved his essence into the Guardian of Tirisfal Aegwyn and from her into her son Medivh, the future last guardian, he still sought to bring the Burning Legion to Azeroth, and Kil'jaeden's demon corrupted orcs seemed like a nice first step. Further, Sargeras might have been trying to get his body back, or at least access to the body he'd come to Azeroth in when he first fought Aegwyn. It would take a Mage to explain it, and I'm from the Warrior sciences. So Sargeras, in Medivh's body, contacted Gul'dan, who was in Gul'dan's body thankfully or this would get very confusing, and suggested that Gul'dan lead his new Horde to Azeroth and crush it in exchange for the possibility of becoming all-powerful by accessing the Tomb of Sargeras. Gul'dan wasn't sure if he trusted this strange wizard from another planet or not (tip: if a strange wizard from another planet offers to make you a god, be sure there's several insanely big strings attached) but he really, really, really really, really liked the idea of being a god. So he eventually helped hook up two ends of a Dark Portal between Azeroth and Draenor, giving us all a snazzy instance to run later, and the First War was on.
Not wanting to risk getting whacked himself by actually going into battle... that's why evil madmen have minions, don't you know... Gul'dan managed to get Blackhand the Destroyer appointed as chief decoy...er, I mean Warchief of the Horde. He also sent Garona to Medivh as an 'emissary', in reality because he really still didn't trust the mage (not that it mattered, because he really couldn't trust Garona either, as she ended up liking Medivh more than him and not reporting back accurately. The problem with being an evil, demented, power-hungry maniac and letting everyone know that you're an evil, demented, power-hungry maniac is that ultimately, when you need friends they're too busy checking the floor for trap doors to help you out) and, while things went well at first... orcs stomped all over Azeroth, kicked Stormwind's butt, the usual... things went bad for Gul'dan when he discovered that the humans had found out Medivh's role in bringing the orcs to Azeroth and, well, they were kind of upset about it and wanted to talk to him. Using swords as words.
Not wanting to let Medivh die until after he revealed where the Tomb of Sargeras was, Gul'dan took advantage of the distraction to try and pilfer through Medivh's brain for the secret. As you might expect, it was harder going to read the mind of one of the best wizards in existence, especially when he also had Sargeras himself hitching a ride inside him: Gul'dan was still looking for the file marked "Here's how Gul'dan can become a god by going to the Tomb of Sargeras' when Khadgar registered his displeasure with his former master via stabbing. It turns out that being inside someone's head when they die isn't a terribly fun experience. Gul'dan went into a coma, and when you go into a coma on the eve of your ultimate triumph, some bastard always comes along and tortures your spies, kills your followers and usurps control of your demon-possessed Horde.
In this case, the bastard (at least from Gul'dan's perspective) was Orgrim Doomhammer. Orgrim was already kind of ticked at Gul'dan for things like tricking the orcish people into eternal servitude to a race of monsters and killing his childhood buddy Durotan, so once Gul'dan took his unexpectedly long nap it didn't take much prompting for Orgrim to kill Blackhand and usurp control. He tortured Garona until she told him who the Shadow Council membership was, and then he killed them too. Gul'dan woke up without his chief decoy, his expendable followers and to find the Doomhammer eager to turn his brains into pudding.
Once again, it was Gul'dan innate genius at knowing exactly when to suck up to people that saved him. Just as toadying to Kil'jaeden had bought him the power he'd needed to eclipse Ner'zhul, now it was Doomhammer's remarkably well-toned hinder that Gul'dan puckered up on. Gul'dan made up a nice story about Rend and Maim Blackhand betraying Orgrim and followed that up by promising to make the Horde new, even more powerful agents of destruction to replace the fallen warlocks who, in dying, had deprived the Horde of a great deal of its magical power. Doomhammer may not have asked for this way, but once in it he intended to win it, and while he wasn't nearly stupid enough to trust the warlock he knew that he needed magic to do that. So he agreed. Gul'dan, being somewhat of a mysical ham, chose to kill two birds with one stone so to speak: he sacrifced his own necrolytes in order to raise his slaughtered Shadow Council minions in the bodies of the falled knights of Stormwind, then placed the eldritch energies of the dead necrolytes into jeweled truncheons that he gave these new 'Death Knights' to use. Doomhammer had to admit these were powerful troops, and Gul'dan smiled knowing that he'd managed to raise most of his dead power base back to unholy unlife at the behest of the guy who'd killed them all in the first place.
Of course, Gul'dan stayed loyal, and the orcs wiped the humans and their dwarf and elf allies off of the face of Azeroth. Then the Burning Legion came and, using their orcish armies, crushed the night elves and destroyed all life on Kalimdor and the Eastern Kingdoms.
Yeah, it doesn't sound like much of a game to me, either. World of Warcraft - The Burned Crusade. Play as... I guess maybe the last Pandaren survivors or something, I don't know.
Of course, Gul'dan didn't stay loyal to Doomhammer. He bided his time until he had what he wanted... control of a power base off of the coast of Azeroth, and two whole clans under his command (the Stormreaver and Twilight's Hammer) and once he had it, he was finally free to act on what he'd seen when he was comatose after probing Medivh's mind. Sailing to the island of Suramar, now raised from the depths of the ocean, he found and breached the Tomb of Sargeras... and got himself eaten by crazed demons for his trouble. Oops. So much for godhood. His act of desertion on the eve of the Horde invasion of Lordaeron broke the back of the Horde offensive on Azeroth, and while they would fight every inch of the way back to Blackrock Mountain, from the moment Gul'dan took his forces and left the Horde was beaten.
Of course, this wasn't quite the end for Gul'dan. Turns out he'd packed so much magic in that head of his that even after the rest of him was chow for nutty demons, his skull was still an item of singular power. After a member of the Bonechewer clan used it as a knick knack for a while, Gul'dan's old teacher Ner'zhul had the skull stolen and brought to him where he would sit and laugh and laugh and laugh at it for hours. Something about 'betray me to Kil'jaeden, will you?' or some such, I didn't catch it all. In addition to berating his once-student's treachery, Ner'zhul used the skull to try and open portals for the orcs to escape Draenor, and it was eventually stolen from him by the Alliance Expedition, who gave it to Khadgar who used its power to close the Dark Portal from the Draenor side.
Draenor blew up, becoming Outland, and somebody grabbed the skull and it ended up in Felwood, where Illidan Stormrage ate it. Well, okay, he really just ate all the demonic magic that was in it at the time, which was a considerable amount, considering that by the time that Illidan found it, the skull was as big as he was, and afterwards the skull was small enough for him to carry it around and talk to it in an opening cinematic. Nowadays, the skull hangs out with Illidan in the Black Temple (ironically, once Gul'dan's headquarters) and while Illidan gained enough of Gul'dan's memories from the skull to have found the Eye of Sargeras, it's unclear if that's all he got or if he acquired some of Gul'dan's personality as well. That might explain a few things.
At any rate, that's Gul'dan for us. Demon-consorting backstabber, creator of the first death knights, power hungry maniac, betrayer and ultimately the cause for both the first and second war and the direct cause of the defeat of the Horde at the end of the second war, and all around terrible, horrible, awful, no good person.