My deck for first time legend.

Gameplay: Play cards on curve, win with Zul'jin or a Highlander card.

Match ups:

Aggro: Explosive Trap, Candleshot Wound Prey and any rush card is a great keep. Against hyper aggresive strategies- like almost any shaman- [Hearthstone Card (Zephyrs the Great) Not Found] is a must-keep for some healing or chomping up murlocs. Then, while not being able to counter all- hope to draw (or search for him! Stitched Tracker ) Reno Jackson. After his battlecry most aggro players will concede, or you can come back with the highlander cards.

Mage: Always keep Flare, Cult Neophyte, Cat Trickkeep Stitched Tracker if you haven't draw [Hearthstone Card (Zephyrs the Great) Not Found] in the mulligan. Here you play as aggresive as possible, or reactive against secret mages. The deck does have a lot of refill, so if you stay alive untill turn 7+ you'll most likely win. Here Zul'jin's battlecry with some extra castig of Flare and some summoned beasts helped me win a lot. For any mage use any discover option to find Pressure Plate, and keep it for key turns, best if you have another spell to trigger their [Hearthstone Card (Counter Spell) Not Found].

Warlock: Pain and discard lock are toss ups, you just have to get lucky. Stealer of Souls is a favorable match up, especially if Cult Neophyte, and Pressure Plate are played beforehand. Large control locks can be won by playing aggresivly, but is often lost.

Priest: Surrender or try, you have to get lucky with the drawn cards.

Hunter: favorable match up, this is almost always the better deck.

Paladin:  Mulligan forWound Prey, Explosive Trap Flare. Handbuff is a bad match up, but most others work great. Kazakus, Golem Shaper is extremly useful here with the deal damage battlecry/freeze or with a taunt.

Card replacements:

[Hearthstone Card (Stiched Tracker) Not Found] - possible the best card in the deck, to discover a copy of a minion in the deck is extremly valuable. Craft it, it's only a common!

Zixor, Apex Predator & Zilliax - this is the rush package of the deck, if you don't own either of them, Diving Gryphon has nothing to pull and can also be replaced. To replace the draw and versatility, maybe include Hunter's Pack or Wandmaker if you want to go more aggressive go Kill Command or Phase Stalker.

Zephrys the Great,Dinotamer Brann, Reno Jackson and Dragonqueen Alexstrasza - All the best highlander cards. If you don't own them, craft them. If you don't have at least 3 of those, the deck is not good.

Nagrand Slam and Zul'jin: They work great together, while Nagrand Slam on is own is okay and sometimes enough to reach a surprising lethal - and almost always enough to clear a secret mage's board - I've mostly included it for it to be played free the second time, since this is an insane finisher off of Zul'jin, especially together with [Hearthstone Card (Leok) Not Found].  If you don't have both, cut them and replace with with a secret package.

Barak Kodobane - while there are scarely any 3 mana spells - only Animal Companion& Olgra- this is a great refill. As a greedy player I'm partial to replace it with Hunter's Pack or Lock and Load.

Kazakus, Golem Shaper: mostly used for healing, card draw or to summon two divine shield/ stealth minions, this card is great and verstatile. An aggresive replacement would be Dragonbane or Kill Command or any secret related card.

Or replace any of these with the some extra secrets: Phase Stalker, Cloaked Huntress, and Eaglehorn Bow or Mystery Winner are all great synergy cards, while Misdirection is surprisingly good.