Deck List to Beat Loatheb in Heroic Mode

The way to beat Loatheb is using one cost minions that have at least 2 health or that have charge. You also need a way to remove the Fen Creeper, an example would be to use Sap. Here is an example of a Rogue deck list:

Rogue Deck to beat Loatheb in Naxxramas in Hearthstone Heroes of Warcraft

2x Backstab
2x Wisp
2x Cold Blood
2x Argent Squire
2x Bloodsail Corsair
2x Elven Archer
2x Goldshire Footman
2x Murloc Tidecaller
2x Shieldbearer
2x Stonetusk Boar
2x Young Dragonhawk
2x Eviscerate
2x Sap
2x Frostwolf Grunt
Goldlight Oracle
Edwin VanCleef

Strategy to Beat Loatheb in Heroic Mode

You need a way to get rid of the Fen Creeper on turn 2. So you either need Sap or Backstab and Eviscerate in the opening hand, with Sap being the preferred card. If you don’t get those cards by turn 2 you are very unlikely to win.

Get a few of the two health minions on the board as soon as you can. After you have removed the Fen Creeper and have around 4 or 5 minions on the board kill the Spore(s), preferable with no mana or minion cost (for example using Backstab). Then beat down Loatheb as fast as possible.