I beat Anub'Rekkhan with an inervate/alarm-o-bot druid, Faerlina with a weenie priest with a few choice heal synergy cards, my lightwarden was a 21/4 when I killed her, and Maexxna with a warrior deck with bouncing heal minions, chargers, weapons and removal, attritioned it to death.
I defeated Heroic Anub'Rekhan and Heroic Faerlina with a "normal" Mage deck.
For the Heroic Maexxna I made a Priester with:
2x Voodoo Doctor
2x Earthen Ring Farseer
2x Mind Blast
= easy win
You let him fill up his board with minions that only have one attack (the Spiders and the Stoneskin Gargoyle) and then you heal yourself. He can hit you for 7 - but you can heal for 8. Burn useless cards so you can pick up new cards until you get minions with charge and of course the 2x Mind Blast. Wait until you and Maexxna have no cards left and wait until he is so low that you can kill him with your charge minions.
For a much, much cheaper way to defeat Maexxna - build a Warrior deck, stock up on Charge creatures, weapons and quasi-weapons or damage spells. Kor'kron Elites are your best friends in the whole wide world.
This deck has a few essentials that don't fit the theme, though, specifically Voodoo Doctors and Cleave.
Maexxna will often lead with some small-time minions like Webspinners, another Haunted Creeper or, if you're lucky, a Nerubian Egg. Yes, lucky - you WANT that threat of a 4/4 hanging over you.
See, here's the thing; it's actually fairly easy to get Maexxna to fill her entire board with 1-damage minions like spectral spiders (hit the first two Haunted Creepers with a Cleave) and Webspinners. At that point, there's essentially nothing she can do but keep punching you. The match turns into a damage race. If you can draw a Voodoo Doctor reasonably early, that plus the Warrior's armor power will drop her damage to at most three per turn, or two if she played a Nerubian Egg. A couple of Shield Blocks will give you a bit more breathing room, but if you really want, you can invest in heftier heals like an Earthen Ring Farseer (dropping her effective damage to one per turn), or even a Priestess of Elune to stretch things out indefinitely.
Once that's done, it's just a matter of throwing as much damage as you can at her. Maexxna doesn't have any heals in her deck, and she'll bounce your Charge creatures back into your deck every turn, so scrounge up every weapon, Charge creature and damage spell you can find - Bluegill Warriors, Wolfriders, Kor'kron elites, Mortal Strike, Heroic Strike, Fiery War Axe, Arcanite Reaper... Really, you can probably make this deck work without spending any dust at all.
Alexstrasza seemed to do most of the heavy lifting for me, while I could relax and focus on minions before plopping her down and reduce the bosses by 30 hitpoints.. This is a cheesy card that circumvents the larger hitpoint pool obviously, but it's by no means necessary.
Some unconventional cards like Mind Control Tech work very well against these bosses. Maexxna can spam your minions back all she wants, doesn't do squat if you take all of her minions.
It took a few hours to burn through all of the first wing including heroics, so I was a bit dissapointed at the massive warning about how difficult it would be.
Basically you use a freeze mage deck to handle the rather heavy minion spam. All the frost you can get + flamestrike and cheap taunts makes for a very easy fight.
Beat him in the first try.
2. Grand Widow Faerlina
Warlock rush/zoo deck along with some removal made this fight very, very easy, practically eliminating her hero power, since my hand was empty most of the time.
Beat her in the first try, though for some reason she decided to inner rage my raging worgen, which along with two power overwhelming's took 28 points off of her. The AI definitely needs some work...
For some reason I thought getting minions back would make this the perfect rogue fight...
It took five tries with one overhaul. Maexxna fairly consistantly puts down haunted creepers, so I made sure that her board was *only* 1-1's. On the fifth try I had the right combination of removal and self-healing with voodoo-doctors/earthen ring farseers, that I could start swapping out for charge minions and use alexstrasza to keep myself alive as well as knock her down to fifteen asap.
This is the cheesiest way of doing it and I can't recommend it.
Just use a freeze mage to handle the minions along with bounced back heals and she's no problem.
Another great guide!
I beat Maexxna with a really cheesy Priest deck. Allowed her side of the board to fill up with 1/1's, used Priest heals and spells to stay alive until I drew Alexstraza then kept playing her until Maexxna died of fatigue damage... I'm not proud of it haha!
Maexxna is really easy, all I did was fill my paladin deck with damage and heal battlecrys; two consecrates to smash open those haunted creepers and flood her board with 1-1's; two humilitys and my aldor peacekeeper (Though all I ended up humilitying was a an emperor cobra) and a bunch of weapons to hit her face. As long as you keep her board full of 1 attack minions it's easy enough to heal more than she hits and wear her down a bit for fatigue which will kill her. I didn't even have an alexstraza and both my truesilvers got burned but I still won by a wide margin.
One other thing I realized later on is that I could have cleared cards I didn't need like my surplus voodoo and elven by playing them then hitting them with an elven to kill them so they don't get bounced back to my hand and fill it up, or even worse kill an enemy and let maexxna play something better.
not the deck I ended up beating the spider with but I had a hilarious scenario of having deathwing being constantly brought back to my hand to board wipe for like 7 turns in a row