Hearthpwn

This is a midrange paladin deck of my own design that uses Prince Keleseth, Sword of Justice, Silver Vanguard and Spiteful Summoner with Dinosize (in your deck) to put sturdy / beefy minions on the board and bring the pain! You need to hold serve for the first 3-4 rounds as the deck really starts to shine in the mid turns.

It doesn't use Call to Arms because of Keleseth and SOJ, and because, frankly, I was getting sick of that card having to be included in EVERY viable paladin deck.

One especially fun combo, if the cards fall just right and you have The Coin, is to Zola your Kelesth on turn four and play him again on turn five. You can also pull this trick in the later rounds making a late Keleseth a little more useful. And don't get me started on the fun that is a 0-cost 7/7 Corridor Creeper thanks to Keleseth and SOJ.

Don't be afraid to use Aldor Peacekeeper early. When buffed by either or both Keleseth and SOJ they make valuable trading tools.

Dinosize is primarily in the deck for Spiteful Summoner but it's a surprisingly good card in its own right. Your opponent rarely sees it coming because not many decks run it and it's been my closer in quite a few matches.

Mulligan for Prince Keleseth (naturally), Righteous Protector, Argent Squire, Sword of Justice, Wickerflame Burnbristle and Stonehill Defender. Keep Rallying Blade in certain situations like when you know it's probable you'll be seeing an early 3-health minion, Corridor Creeper and considering keeping Zola the Gorgon if the rest of your hand is solid. If you have too many high mana cards in your opening hand, put her back. She's valuable early and late, which is why I think she's such an underrated card.

And one final note of advice, don't be TOO greedy with Sword of Justice. There can be a temptation to sacrifice tempo when using it. Don't. It's there to help you hold the board until you can get to the really big guns. Use it with hero power if you need to and use the weapon if it enables you to take an enemy minion that's down to one health off the board.

Can I guarantee you'll reach Legend fast and easy with this deck? No. If you're looking to do that go play murloc paladin. Can I guarantee you'll have FUN playing this deck? Why yes I can. When it clicks, it clicks hard.

Up votes are, of course, appreciated.

UPDATE: -1 Divine Favor, -1 Silver Vanguard / +2 Acolyte of Pain. This gives the deck more reliable card draw and early round stability as well as better synergy with Prince Keleseth and Spiteful Summoner.

UPDATE 2: -1 Bonemare / +1 Spellbreaker. This deck already has a really strong late game and Bonemare was just piling on. Rather than more power what this deck needed was more utility, hence the update. With Keleseth or SOJ, a 5/4 with a Silence is one hell of a minion.

UPDATE 3: -2 Argent Squire / +2 Benevolent Djinn. A little more suvivability. Buffed by Keleseth and/or SOJ they're even harder to take off the board.