What: An eredar, one of a race of magical creatures that lived on the planet Argus.
History: The planet Argus was a peaceful place, full of highly intelligent magic-users that called themselves the Eredar. Kil'jaeden was known as a "genius among geniuses", and along with his friends Archimonde and Velen, eventually became one of the leaders of Eredar society. Then one day, the three pals were contacted by the fallen titan Sargeras. "Hey, guys," Sargeras said, "I noticed you're pretty skilled at using magic. How about becoming loyal to me, and in the end, you'll end up famous and powerful, and will in no way end up killed at the hands of twenty-five nameless adventurers?"
Kil'jaeden and Archimonde agreed to this devil's bargain, while Velen secretly made a deal with Sargeras's enemy, the Naaru. As the rest of the Eredar were getting their demonic powers, Velen took some other Eredar who had decided against Sargeras and did a runner. Kil'jaeden was not very happy with his old buddy, and chased the non-demonic Eredar (soon to be Draenei) across the realms for five thousand years. Man, and you thought we've been taking a long time to catch Osama Bin Laden! And just like Bin Laden, Velen escaped Kil'jaeden's pursuit and went on to the planet of Draenor. Well, I guess only the first part is like Bin Laden. He's not on Draenor, as far as I know.
Note: This whole storyline was "retconned" for the Burning Crusade, so that the draenei made sense in their current form. In the original lore, the Eredar were the ones that corrupted Sargeras, so in that storyline, Kil'jaeden would have just been evil from the beginning.
Kil'jaeden had gotten his promised position of power in the Burning Legion, but he sat on the sidelines while Sargeras used Archimonde and some of his other lieutenants to attack Azeroth in the War of the Ancients. Luckily, this also meant that Kil'jaeden was untouched by Sargeras's anger when that invasion failed. Realizing that brute demonic force might not be enough to take down Azeroth, Sargeras asked Kil'jaeden to recruit him a mortal army for the next try at invasion. After scanning the cosmos for a long time, Kil'jaeden found a world that spoke to him ... Draenor.
Kil'jaeden went down to Draenor and noted that the orcs and the draenei were living peacefully in shamanistic societies. Why he didn't immediately destroy the draenei, who he'd spent thousands of years chasing, is anyone's guess. Instead, he decided that he would corrupt the orcs and turn them into the fighting force he needed. He disguised himself as an orc ancestor, he managed to convinced the orc clan leader Ner'zhul that the draenei were plotting against him. The orcs took him at his word, and began to attack draenei clans, enhanced by Kil'jaeden's gifts of shadow magic and bloodlust. But Ner'zhul got cold feet and tried to back out. Kil'jaeden instead offered a deal to another powerful orc, the warlock Gul'dan -- power in return for loyalty and wiping out the draenei. Gul'dan accepted. Kil'jaeden gave the blood of the demon Mannoroth to the orcs, and they wiped out nearly eighty percent of the Draenei of Draenor in one last battle.
Sargeras hadn't spent this whole period just sitting back and watching Kil'jaeden do his dirty work. He had gone down to Azeroth, fought the Guardian Aegwynn, and let her kill his physical body while possessing her spirit. In time, Aegwynn had a son, Medivh, and Sargeras worked through that powerful sorcerer to help destroy Azeroth. Medivh and Gul'Dan worked together to open the Dark Portal between Draenor and Azeroth, and the Horde (trained by Kil'jaeden) wreaked havoc on Azeroth. Pleased with his work, Kil'Jaeden went back to wherever the Legion commanders hung out and settled down to watch the mayhem. But Medivh was assassinated during the First War, putting Sargeras out of the picture, and Gul'Dan's mad quest for the Tomb of Sargeras doomed the orcs in the Second War. The Horde had failed, and the remaining orcs were placed in internment camps.
Kil'jaeden was in a tough spot. His big plan had failed, and Sargeras would certainly be after him for ... oh, wait, Sargeras is dead/incapacitated. Well, guess who's leader now? The orcs failed, so it was time to make a bigger army. A better army. The type of army that would take orders, that wouldn't complain, that could destroy Pittsburgh in a mad hunt for brains. Yep, it was time for the Scourge.
Kil'jaeden sought out his old enemy Ner'zhul, and tortured him until his body died but his soul remained. Kil'jaeden then offered Ner'zhul another deal -- keep getting tortured for eternity, or command an army of undead for the Legion. Ner'zhul picked the latter, and was transformed into the Lich King. But Kil'jaeden didn't entirely trust him with a body, so he set Ner'zhul's spirit inside a frozen crystal with a suit of armor (I dunno, maybe he looked bad naked) and some dreadlords to keep him from slacking. The Lich King sent out a plague of undeath, and with lieutenants like Arthas and Kel'Thuzad, managed to raise a sizable zombie army and raze a lot of Lordaeron and Quel'Thalas.
After lots of destruction, mayhem and brain consumption, the Scourge finally stole a spellbook of Medivh's, and Kel'Thuzad summoned Archimonde the Defiler into Azeroth. In order to get everything more firmly under the Legion's thumb, Archimonde transferred control of the Scourge to Tichondrius and the dreadlords. But Archimonde -- never a great tactitian -- forgot to do anything with the Lich King, leaving him free of Legion influence. Looking for revenge and a way out, the Lich King dispatched Arthas to tell Illidan about how the Skull of Gul'dan can be used to defeat Tichondrius. Illidan did as requested and knocked off the powerful demon lord, while his brother Malfurion, Thrall, and Jaina Proudmoore blew up Archimonde at the Battle of Mount Hyjal.
The third invasion had failed, and Kil'jaeden was ticked off. But after seeing what had happened to his pal Archimonde, he wasn't about to go to Azeroth himself. Instead, he offered Illidan his usual deal (untold power vs. eternal torment) and sent the renegade elf to take out the Lich King. Illidan tried to use magic to tear apart Northrend and destroy the King, but was stopped by his brother and took off to Draenor. Kil'jaeden must have chuckled at that turn of events -- how was Illidan going to hide from him on Draenor of all places? He waited until Illidan had killed the pit lord Magtheridon, and then appeared to the elf and told him that he had better go back to Northrend and try again, or he'd be fired. Out of a cannon. Into the sun. Illidan actually managed to get to Northrend before he got his ass kicked this time, but he still fell to Arthas, who fused with Ner'zhul and created a powerful, mobile Lich King Prime. Illidan scampered back to Draenor in defeat and is now trying to build an anti-Legion army.
Where he is now: Your guess is as good as mine. He's still commanding the Legion, but there's not much of a clue as to what the Legion's home planet is.
Identifying characteristics: Big, red, demon-looking. Seems to have a lot of horns. He is able to change his size, and probably his shape, to suit the occasion. He is a master of arcane and shadow magic, and managed to enslave the dreadlords, which means he's pretty powerful. While there's not a lot of details on his exact powers, he's extremely intelligent and good at trickery, which may do you more good overall than having a lot of destructive spells. He is also more subtle and forgiving than Archimonde, and seems to not desire much power or fame for his own aims.
Why we're not going to kill him anytime soon: Well, he's currently the head bad guy of all Bad Guys, so we should probably take him out. The Legion is gaining more influence in the Outlands, and can possibly push through the Dark Portal to get to Azeroth again. But Kil'jaeden himself is nowhere to be seen -- he's never physically fought in any of the wars. There are a couple things that might get him to manifest himself, however. He's not particularly happy with Illidan at the moment, and he may wish to deliver some personalized punishment for the elf's repeated failure to kill the Lich King. And Kil'jaeden's archnemesis, Velen, is now head honcho of the Draenei on Azeroth. Kil'jaeden is usually good at keeping his grudges out of the overall business of the Legion, but it might be hard to resist the call of revenge when you find out that the guy you chased for five thousand years is now living, metaphorically, in the apartment next door.
For more information: WoWWiki on Kil'jaeden, Wikipedia on Kil'Jaeden, Worldofwarcraft.com on the Burning Legion.