Hearthpwn

I got to Legend using this and a Murloc Pally deck. 

Around rank 4 I was running into too many hungry crabs and freeze mage to keep a decent win rate with the Murloc Pally, and the primary became the priest. The win/loss stats, which aren't detailed since I primarily play HearthPhone, are as follows:

Pally Murloc: 28-11

Priest: 37-17

 And here's the pally 

The preliminary tips:

1. Swim with the current: Adapt. Track your games. Get HearthStats if you play on computer. If you play on your phone like I do, a simple deck tracking app is fine. Get 2-3 consistent decks and pay attention to your winrate - keep it over 60%. Once you hit rank 5 you no longer get bonus stars for win streaks. If you lose 2 consecutive games with a deck, switch to the other. If you keep losing, take a break, play casual, take more Adderall - just don't undo your work with a losing streak. It might take 30 games for you to climb to rank 2, and an hour of frustrated losses to pirate warriors to fall to your rank 5 floor. 

2. How do you catch a unique rabbit? Unique up on it. How do you catch a tame rabbit? The tame way - unique up on it. With this deck or any web deck you're given the framework for a deck mechanic that someone else had success with. Depending on your playstyle and the day's meta you can tweak the recipe to throw off the meta and take people by surprise. If 75% of the games you're​ playing are against someone with ice block then throw in a secret eater. If you're getting blown up by pirate warriors then run a gluttonous ooze. They deserve to have their game ruined because they've never had an original thought in their life, suck at video games, and type 35 WPM.

3. Don't chase the shiny object: Especially with this priest. You're going to be tempted to Mulligan poorly when Lyra or Burgly Bully ends up in your starting hand. Don't keep a card just because you like it. It will show up soon enough. Use discover to get cards you can actually use. If you cast shadow visions on turn 1-3, you probably have better, more immediately effective options than dragonfire potion. When you discover a dragon, don't fool yourself into getting a 9-10 drop you might never have the board control to pile on. 

4. Your opponents are usually predictable: you know the meta and off the bat you will have at least a 50% chance of guessing their deck mechanic before they even play a card. If you see a rogue, get your potion of madness ready so you can steal his igneous elemental and ruin his generic quest deck. If a warrior goes taunt, you know he has a lot of high cost cards with 3 or less health.

Tweaks

As I said earlier, the deck posted on here lists the framework of a successful mechanic and can be changed around to fit a) the current meta at your rank and b) your deck collection if you didn't want to give Blizzard all of your money to get all of the cards. 

I'll start by listing the essential cards. I would highly recommend not replacing these cards, and would say that you won't achieve the right mechanic if you aren't running them. If you want to run this deck I would suggest getting these cards first: 

Northshire Cleric

Potion of Madness

Power Word: Shield

Radiant Elemental

Shadow Visions

Shadow Word: Pain

Shadow Word: Death

Drakonid Operative

Holy Nova

Lyra the Sunshard 

Dragonfire Potion

Netherspite Historian

Twilight Drake

Primordial Drake

Then there are the tech cards. This is where you can get a little more creative. Try not to throw off your curve by replacing a low-cost card from the recipe with a high cost card. A lot of people are asking about replacement options. Here are a few suggestions:

Curious Glimmerroot can be replaced by a few cards that offer synergy and class-counter. You can add an additional Priest of the Feast for a cheap, simple replacement. You can also try running Gluttonous Ooze if you get fed up with Pirate Warriors. 

I highly suggest running at least one Priest of the Feast in this deck, since its main focus is to maximize the number of spells you cast. But if you want to be sneaky you can also run Barnes and try to summon a game changer like Lyra, Burgly Bully, or Ysera. Moreover, you can increase the survivability of a 1/1 drop with Power Word: Shield. 

Eater of Secrets was added to my deck at around rank 3 when I started seeing Mages running Ice Block in over 50% of my games. From what I've seen, the meta has "chilled out" (dad joke) on the Mages, and it might be safe to take the card out. 

I really like Burgly Bully with this deck and I don't suggest taking him out. You'll see the true value when your opponent gives you multiple coins and you play Lyra and Radiant Elemental. You use coins to create spells while you simultaneously gain mana to use some of the middle-cost spells that might pop up. Right now I have 1 in my deck but I've also run it with 2. You just need to be careful of having too many cards in your hand. 

Ysera and Arcane Giant are cards that you can replace without worrying about throwing off your entire deck mechanic. I like Ysera for the low-cost spells she can generate, but you can also discover her. Feel free to take out one of these cards and replace with an extra Primordial Drake, Elise the Trailblazer, or a Gadgetzan Auctioneer. 

Tweaks I dislike: 

I've played against some people running Loremaster Cho in their priest decks. I suggest not doing that. Cho is a double-edged sword, and your deck has a lot of cheap spells that will be readily-usable to the opponent if you cast them. 

Update 6.2.2017: The current build. I'll post my record from 5 to legend when (if) I get legend this season.