Hearthpwn

Introduction:

This deck is intended for the Heroic version of Terestian Illhoof. It should also breeze through the normal version if you're having trouble with that.

If you don't have the older expansions, check below for a Standard Version of this deck.

Also check below for a video showcasing the deck against a rather nasty enemy draw (7 Imps on turn 3). 

Basic Gameplan:

Steal his imps. Stay alive. :)

Mulligan for Shadow Madness, Lil' Exorcist, Deathlord, Power Word: Glory and Mind Control Tech. Early on you want to prioritize getting imps of your own and minimizing the damage you take.

If you have the option, play Deathlord before Exorcist so that you can play Exorcist when there are more enemy Imps on the board.

In case you don't already know, if you Shadow Madness his imp and get it killed, it respawns on your side. Be aware that if you use Power Overwhelming on it, it will return to his side before dying to Power Overwhelming. 

Note that the AOE clears like Excavated Evil or Shadow Word: Horror are more about bursting Illhoof's HP than actually "clearing" the board (since the imps just respawn). If you have minions of your own be sure to attack with them before using an AOE clear to get extra value from it.

Try to save Resurrect for when you are likely to get an imp from it.  

Play Baron Rivendare when you have at least one imp of your own, he'll cause your imps to multiply. 

About the Opponent:

Pretty aggressive deck, mostly by means of minions, many of which have Deathrattle. Starts the match with 1x Icky Imp on the board. The biggest minion I've seen him play is Doomguard. The only notable burst from the hand I ran into were Power Overwhelming, Steal Life, and Soulfire.

Note this fight can have a great amount of variance to it. While I was experimenting with it, there were attempts where he only had 2 imps by turn 10, and others where he had 5 imps by turn 2. If he has a very strong start and you draw poorly, it's entirely possible to get run over. Don't despair and just restart.

About the Deck:

Priest deck focused on stealing Icky Imp and using them against their (former) master. Most of your damage against the boss will come from your stolen imps as well as aoe board clears that can kill his imps and your own. You also have defensive cards like Priest of the Feast, Power Word: Glory, and Flash Heal as well as taunts like Lil' Exorcist, Deathlord and Abomination to help keep you alive. 

Note that at the moment Abomination seems to break the AI and (sometimes) stop it from attacking, this may be changed later but the card should still remain quite useful. However also keep in mind Abomination does damage to your hero as well, and the AI will probably go through it if he realizes he can finish you off.

For a Standard Version: 

If you don't have the older expansions, try the deck with these changes,

-2 Lil' Exorcist

-2 Deathlord

-1 Lightbomb

-1 Baron Rivendare

+2 Mindgames

+2 Defender of Argus

+1 Cult Apothecary

+1 Resurrect or Cult Apothecary

Other cards to consider:

Mindgames Can get you something useful like an Imp or Doomguard. I removed it because it's slow and it can also just get you a Voidwalker.

Antique Healbot good option if you feel you need more self-healing.

Sludge Belcher good option if you feel you need more Taunt.

Defender of Argus another good Taunt option

Unstable Ghoul decent early taunt option, the whirlwind effect can do a bit of damage to the board, but I cut it from my list because Lil' Exorcist is better.  

Annoy-o-Tron decent early taunt option, the divine shield offers the vague possibility of stopping a 6 attack imp or a Doomguard, but I cut it from my list because Lil' Exorcist is better.

Explosive Sheep The explosion can deal massive damage to Illhoof, but I cut it in favor of Deathlord since I feel that once you have established control of the board dealing damage to Illhoof is quite easy anyway, and Deathlord can help you survive long enough to get to that point.

Kel'Thuzad pretty much a slower version of Rivendare in this matchup.

Thoughtsteal I initially included this because it fit the theme, and it can help you some useful cards, but an early stopgap like Power Word: Glory is far more practical.

Feel free to suggest other cards you found useful in the comments.

Conclusion:

Depending on how both you and the opponent draw, this match might be very easy, or very difficult. But this deck was a fun one to use for me, and it should lead you to victory.

Good luck! If you find this deck and/or guide helpful I would very much appreciate it if you vote it up. Thank you.