I took a crack at Heroic Grobbulus in the Construct Quarter of Hearthstone’s Naxxramas adventure and found out that an Inner Fire/Divine Spirit Priest deck works consistently.

Here is the specific deck list I used, although many variations could work:
Circle of Healing x2
Holy Smite x2
Inner Fire x2
Power Word: Shield x2
Divine Spirit x2
Shadow Word: Pain x2
Lightwell x2
Nerubian Egg x2
Shadow Word: Death x2
Dark Cultist x2
Deathlord x2
Stoneskin Gargoyle x2
Auchenai Soulpriest
Lightspawn x2
Holy Nova x2
Mind Control

The strategy is the same as any other Inner Fire/Divine Spirit deck. Create a minion too big for your opponent to deal with and then tear him down.

The problem is that when you face Grobbulus it isn’t clear whether you should be healing yourself or the big minion.

The fix for that issue is having the big minion be Stoneskin Gargoyle. It’ll heal itself and you can always heal yourself.

While the deck works, I felt unsure about some of the parts of it.

Often times when I played the Nerubian Egg, all the Nerubian would be capable of trading with would be the slime produced by Grobbulus’ hero power killing the egg.

Lightspawn felt a little bad because it gets weaker as it takes damage. It was an even tougher choice of whether I should heal it or myself.

Mind Control also felt a little odd, but I put it in there in case I needed to clear a taunt on Grobbulus’ side to secure lethal. I suppose a silence effect would’ve worked just as well.

I might substitute in a little more draw to get the Inner Fire combo faster.

Otherwise it was a simple strategy that got a simple victory. Enjoy!

-Mister Ed