Hearthpwn

I just took same deck I won Chromaggus, (and about 50% of heroic bosses from all adventure's): Control Cube Warlock, just try 4-5 time's

AAEBAf0GBqMB4KwCycICl9MCneIC2+kCDIoB9wS2B44O3sQC58sC8tAC+NACiNICi+EC/OUC6OcCAA==

AAEBAQcE+AewFeCsAqLHAg1LogSRBv8H+wz+DYEO+BGCrQLGwwLMzQKOzgLP5wIA

https://imgur.com/nTKCgBz
https://imgur.com/l172E4m

fatig war, heroic

The easy way:

Warrior Quest !!

https://imgur.com/a/YMpa6

Warrior Quest worked fine for me :) if you like, you can check out the deck I used here:

http://www.hearthpwn.com/decks/1049607-heroic-nefarius-quest-warrior

i just copied the deck from cocos123, sadly i didn't had any moltens, guess they are very important at this deck so i put arcane giants instead. he just missed his lethal phew! :D

http://imgur.com/a/9nLys

Lord Vorctor Nefarius was one of the BRM bosses that causes me some headaches, however, I was able to beat him using this variation of C'Thun Priest. The good thing is that this deck uses only cards available in the standard format (Oct 30, 2016).

Strategy:

In the early turns, try to clear the board by any means possible while you try to heal yourself to survive. You can heal yourself by using Hero Power, Priest of the feast + any spell, or by using Twilight Darkmender's battlecry (it's important your C'Thun reaches 10 attack ASAP).

In case you need to clear the board, don't hesitate to use your C'Thun. Even if Nefarian destroys C'Thun, you can use one of your Doomcallers to return your C'Thun back to your deck.

When you reach around 9 mana crystals, Nefarian will be running out of steam, and he would be unable to clear the board effectively. That's the moment when things move on your favor to beat him.

Here is an up-to-date modified working fatigue warrior version if you need ;)

This Deck did it for me. 

C'thun Priest does pretty well. I won second go with the current meta.

 Yo Here is Nefarius's actual decklist:

Minions:

Twilight Whelp x2, Faeire Dragon x2

Blackwing Technician x2, Hungry Dragon x2

Twilight Drake x2, Blackwing Corruptor x2

Dragon Consort x2, Drakonid Crusher x2

Volcanic Drake x2

 Spells:

Claw x2, Cleave x2

Bite x2, Tail Swipe x2

Dragon’s Breath x2, Flamestrike x2

Got him with an Astral Communion deck that I built to beat (unsuccessfully) Heroic Chromaggus. I caught a break when Nefarius played Astral Communion himself and discarded his hand. Since he already had 10 mana, it did him no good at all.  

Got any new ideas now that year of the Kraken has made these decks obsolete?

This is the pain I'm going through now. Let me know if you find anything. Right now I'm using priest. If I beat him with this deck, I'll post.

I went the Druid route and won: http://www.hearthpwn.com/decks/551268-heroic-lord-victor-nefarius-mill-control-post-old

Loatheb, Grove Tender, Sludge Belcher, Healbot, and Poison Seeds are all Wild now. Innkeeper won't let me use Wild decks. Is there something I'm missing?

You should be able to use wild decks for solo campaign because I'm using wild decks for LoE.

Don't know why I couldn't use Wild decks at the time, because yes, they do work now.  Not sure if my app needed to be updated or something, but either way, I beat him a few weeks ago with Priest. Can anyone confirm if there was a time period where wild didn't work? I don't think I'm making that up.

Thank you for the link, Dude! This deck worked like a charm :)

First try, great deck indeed.

got him with this deck

http://www.hearthpwn.com/decks/464804-heroic-lord-victor-nefarius