Hearthpwn

Thank you man! That 57/57 C'Thun combined with Brann Bronzebeard did the trick for me. Finally I got that Cardback since I just could not beat that boss before. Only had to swap two cards, as I only own one Circle of Healing and no Sunwalker, and I did not want to spend any of that precious dust before the next expansion. A second Psych-o-Tron and an Ancient of Blossoms worked just as well.

Hoooly shit thank you so much for this tweak, I tried everything but this was the first deck that actually worked, let alone the first deck that got even remotely close!

WOW thanks! Only took 3 tries. I've tried about 30 times with other net decks and this was the first that worked. Was at -6 fatigue but got there in the end with a lot of healing.

 fck this heroic boss! all about luck ! and rng fck this

 FINALLY!! Wow this heroic boss was a total pain in my tushy lol

I don't have any medic cards so I put in 2 Disciple of C'Thun as suggested in the comments. I also mulliganed for PW:G also suggested in comments. Thank you to those who contribute to the community! <3

After over a hundred tries with several other (C'Thun) decks, this deck worked for me on the 3rd try. My C'Thun had 48 attack, I played Emperor around the 8th warrior round which then made my Brann free for the prince. I was able to take the prince out on his 1st round. WOOT! Thanks for the deck & GOOD LUCK peeps!

Anyone saying they got this in 2 tries and that the AI let them buff the hell out of C'Thun is clearly trolling.  The AI is never as dumb as stated, and never leaves the critical minions on the board.  After about 100 attempts, I managed to get board control one time and buff C'Thun to 46 with a 0 cost bran ready to go.  Sadly my C'Thun was apparently in my last 5 cards and I could no longer keep up with the face damage.  I would have died from Nazra next turn, so I killed her and prayed, and I still didn't draw the C'thun.  I have spent days attempting to get this or any other deck to work.  If you actually got this, explain exactly what happened or post a video from AFTER they patched the AI to be less stupid.  I have managed to take out every other boss in every other heroic with far less difficulty, and something is just plain wrong here.   

Works very well. Only took 3-4 tries and costs very little.

I ended up putting two Hooded Acolytes down with two Twilight Elders and let C'Thun built up while keeping Nazra at 1 HP. You can put Powet Word: Glory on the charge minions she summons and they're too dumb to realize it and go face often, which builds your C'Thun more and more. Tournament Medics are also good at that point because you can use your hero power on your face and increase C'Thun by 4/4.

Once I reached the point that I couldn't survive Nazra anymore, I hit her face to bring out Malchezaar. He casts Twisting Nether and hero power immediately, leaving the board empty except for his two 6/6s. At that point, drop C'Thun. Mine was at 48/48, so it didn't kill him that turn, but it cleared the board and made it so I could just go face next turn. Easy.

Wasn't as consistent as other comments made out, but got it after 6-7 tries.

I found you should probably mulligan pretty hard to get Power Word: Glory on an early Orc so that it actually heals you when it goes face.

If you play a Lightwell on 2, I found it always just died. Needed a Divine Spirit and then they would just ignore it. The AI seems to basically ignore non-taunts with more than around 4-5 health (with the exception being Lightwell, probably due to 0 attack), so you want to keep your core buffing engine components at this level of healing or you'll lose them.

Had a few games get past 6 turns, and they usually went pretty good, but never quite got a C'Thun buffing engine going. I eventually had two Tournament Medic and two Hooded Acolyte on the field at once for some pretty crazy healing and buffing.

It was rough, and I was on the edge of my seat, but ended with a 57/57 C'Thun discounted along side Brann Bronzebeard letting me OTK Malchezzar after the transition :)

Awesome deck, I used the one on the description but with two Disciple of C'Thun in place of saboteur, finished the orc with a 74/74 C'Thun and just played it on Malchezaar.

Thanks for the awesome deck. I had to craft a few cards - 160 dust but worth the win. It was only this Heroic battle that I couldn't win hence I came to check it out here. First try - accidentally killed the Warrior so Cthun was low. Second try - Cthun was bottom of the deck (last 4) gosh it came right after Malz appear since the Warrior fatigue herself to death. Funnily, Malz didn't destroy all minions, he used a different spell.... didn't matter thought.