Not first time legend, but first time legend with Priest.
After a period of trial and error I came to this version of Resurrect Priest. It seemed superior to any other Priest deck I had ever played, so I played it straight from rank 7 to legend with a 69% win rate.
Always keep Injured Blademaster, Auchenai Soulpriest and Priest of the Feast.
If you have any of the above, also keep Resurrect.
If you have Auchenai, also keep Circle of Healing.
If you have Circle, also keep Embrace the Shadow.
Keep Excavated Evil against Shaman, Mage and Warlock.
Shadow Word: Pain:
Always keep it against Shaman, Mage, Warlock, Hunter and Warrior.
Against Druid and Priest keep it only if you already have a good hand.
Never keep it against Rogue and Paladin.