Legendary Nefarian and Onyxia Paladin Deck (Heroic Mode)

Strategy

Nefarian is a three stage fight, and the key to the battle is managing the three phases efficiently. At the end of the second phase, after Onyxia transforms back into Nefarian, your board will be cleared. This is the key point of the fight, and is where the card Kel'Thuzad comes into play. Your goal will be to build a large board through the first two phases of the fight, allow your board to be wiped, drop Kel'Thuzad, and end the turn, reviving your entire board and consolidating your win.

Another key card here is Harrison Jones. Although the boss can be defeated without it if you do not have access to it, timing the transformation into Onyxia correctly, so you can immediately destroy her weapon and draw 6 cards with Harrison Jones, is extremely powerful.

Aside from these points, the fight is a fairly straightforward battle for value, with Equality/Consecration and Mind Control Tech being your insurance policies for the points where the boss gets too far ahead.