Best Deck to Beat The Four Horsemen in Heroic Mode

The Four Horsemen (Baron Rivendare, Lade Blaumeux, Sir Zeliek and Thane Korth’azz) are completely reliant on minions to kill you so an anti-minion deck is optimal. The best deck to beat The Four Horsemen is a modified version of Freeze Mage shown below. Other decks that might work is a Priest using the many methods to kill low attack minions or Warlock Handlock.

Beating Instructor Razuvious in Heroic Mode: http://wp.me/p1SfP0-1Lu
Beating Gothik the Harvester in Heroic Mode: http://wp.me/p1SfP0-1Lt
All Naxxramas Heroic Mode Guides: http://wp.me/P1SfP0-1L4

The best deck to beat The Four Horsemen:

Class: Mage.
2x Ice Lance
2x Frostbolt
2x Acidic Swamp Ooze
Acolyte of Pain
2x Arcane Intellect
2x Frost Nova
2x Ice Barrier
2x Ice Block
2x Earthen Ring Farseer
2x Cone of Cold
2x Fireball
2x Azure Drake
2x Blizzard
2x Flamestrike
Alextraza
2x Pyroblast

Best Strategy to Beat The Four Horsemen in Heroic Mode

You will need to stop the incoming damage from The Four Horsemen as soon as possible. That means playing Acidic Swamp Ooze early to destroy the Runeblade and  Frost Nova on turn 3 and 4 and Blizzard on turn 6 and 7. On turn 8 play Flamestrike which will kill the three minion Horsemen. In the other turns play the secrets or the draw card cards. If you have lethal on turn 9 using 2x Frost bolt and 2x Ice Lance thats good, otherwise play Alextraza and either heal yourself or put Baron Rivendare to 15. This should enable turn 10 lethal.

Note that it might take a few tries and a good starting hand to beat The Four Horsemen, especially since the strategy above requires specific cards to work well.