Hearthpwn

I made a Grand Archivist deck, works wonders.

lmao i was very lucky, he had like 6 turns to topdeck but luckily he only draw his minions: http://imgur.com/a/T3act GG! =)

[HEROIC] Found a cheap deck, but you will need a lot of patience and RNG. Good luck.

Some tips:

Arch-Thief Rafaam: Always pick Lantern of Power for extra burst, the 3/3 mummies are too slow and will be removed by Flamestrike most of the time.

Alexstrasza: It's a must have because the 35 point of damage is very hard to replace. I had to craft her specially for this heroic.

Onyx Bishop and Resurrect: Great tempo cards since it can bring back your Sylvanas Windrunner or Ragnaros the Firelord, and the 3/4 body of the Bishop will be more useful than you think. And I didn't put Doomsayers in this deck because not only they get easily removed they also mess with your resurrection targets.

0/10 points for this boss.

i dusted my Majodomo as i needed to create a good deck. this boss is impossible without it. other ones have unique minions, powers, even when it seems impossible it is still fun, you can use different tactics to kill them. this one... %#^$

when he finally turned into Majordomo i had 3 mana and could not use my Pyroblast, my hart skipped a beat. No I do not want to play you again!

My answer:

I think the boss card lists for Normal and Heroic are reversed--I have definitely seen two Flamestrikes and two Drakkisath's Command in his deck on Heroic.

If you have a little patience, you can pull off a turn 2 win.

On turn 1, play an 8+ attack minion. Hope Drakkisath plays Mindgames and gets Majordomo Executus and doesn't kill your dude.

On turn 2, kill Majordomo Executus with Big Game Hunter, Shadow Word: Death, Naturalize, etc. and go face.

Varolie posted a good priest deck above that's kind of the same idea. I just lucked out and killed Drakkisath first time on turn 2 with a mountain giant.

I tried your method for maybe 10 times. Must have patience to wait for the perfect combo for you and him. Also one ust be lucky to for Drakkish to Mindgames and get Majordomo Executus.

In my case, I Mind Control his 7/7 minion on turn 2 and Shadow Word: Death Majordomo on turn 3. Afterwards, managed to draw Mind Blast and killed him the next turn.

Ha! I can't believe it worked! Wasn't Turn 2 but still worked out. Took about 10-12 tries. I only had 2 minions in my Priest deck: Rag and Majordomo. I had my Rag on the board Turn 1, and I stole his MAX turn 2 with Mind Control. He had another minion out as well. THen he Mindgamed my Majordomo from my deck to the board. 

I hit his Majordomo with the stolen Tank MAX which transformed him to Rag, then I prayed MY Rag minion would shoot face! HE DID! Win! Thanks ZEF! Ding ding!

 Similar to the others, simply a deck of legendaries and big hitters, with Alex thrown in for an easy win if drawn early.

More legendaries pl0x.

Still working on collecting them all. I have terrible luck with legendary drops. ;-)

Try with this deck. Very little RNG involved. Much easier than the KT strategy.

Toughest match for me by far. Your deck out of many others was the most successful. Thanks!

SO how does one get there deck on the winning deck lists,

The strategy used by this deck is fun, takes advantage of Majordomo executus, anyone can cheese the majority of the bosses with kel+taunt, this strategy is unique to this encounter

5th try does it for my ... at least one usage for Majordomo :D

This was beautiful! Turn 1 i used Thoughtsteal  and get his spell Drakkisath's Command.  He plays Force-Tank MAX. Turn 2 I steal it with Mind Control. He uses Mindgames gets Majordomo Executus. Turn 3, Kill it with Drakkisath's Command and go face. Next turn Mind Blast xD

I just entombed on turn 2.
he played mindgames and got the entombed card... i drew lightbomb. fml am i right? T.T