Hearthpwn

When you first think of how to get rid of 4/4 swarm easily, you would likely imagine Mage's Flamestrike. And in no way would you think of Priest capability of beating Anub'Rekhan, because, duuh, that's priest, and there are primarly 4 attack enemy minions on the field - too much for Pain, too little for Death.

Nevertheless, control combo-priest has huge benefits:

• his very own 4 hp mass-removal with Auchenai Soulpriest and Circle of Healing
• strong minions (and mostly independent), for which the boss has no proper removals/silences, and those just clear the board and get healed/buffed, allowing further board developing

The deck-list is tentative and exactly the same as I've beaten the boss with, and may get more thought into it. This variant is more of a combo-ish, because I threw out my Shadow Words: Death and 2-drops and included things like Inner Fire, Circle of Healing and Divine Spirit. Still don't know about the first, probably they are of little use against Anub'Rekhan, but Circle and DS always work like a charm, giving huuuge value.

Holy Smite was included as an option of removing small-but-nasty stuff or finishing off something bigger. Shadow Word: Pain is very good in removing Deathlord with cool (for us) deathrattle. AR tends to play it a lot, so huge chances to get a lot of value here. Holy Fire is always a removal + heals you, helping you to avoid quick casual death. Holy Nova was avoided because of very little use - boss has no low hp stuff to wipe with it, au contraire, he often plays Nerubian Egg. Urgh.

Shieldbearer and Prophet Velen are both questionable, but cool cards in this deck for obvious reasons. Draenei can roll early comboing with buffs and get free cards with the help of Northshire Cleric, or he can defend valuable stuff from gruesome fate later in the game, in case we can't heal everything in time. Velen is huge minion himself (imagine you get him from Deathlord), also hooray Circles for 8 hp, Fires for 10 damage and 10 hp heal.

Key-carry card happens to be Gurubashi Berserker. Nuff said, you just can keep him alive and clear stuff right up to the point you one-shot poor Anub'Rekhan. I had only one, you can consider having more.

One more card I would consider having here is Defender of Argus. Sadly, I have none in my collection and don't feel like crafting it. But you should try it, no doubt!

If you have any questions/suggestions/angry reviews, please, write them down in the comments (that's my first guide anyway). GLHF!