The shrine can be found in the Shaded Woods area. You’re best to go from the second bonfire (the one with the 3 nearby exits) and head through the archway with the Goblins running around outside.
Be wary as you head around the right-hand corner though as you’ll spot a Flexile Sentry (and it’s harder to beat as the sword-bearing side seems to face you more often). There’s also another Poison Goblin hidden a bit further down on a path leading right to where we want to go.
Don’t forget to grab the [Dragonslayer’s Crescent Axe + Golden Falcon Shield] from the ground before heading up to the shrine itself.
Note: You can open the large doors here without all four primal boss souls in your possession. If your overall Soul Memory (total number of souls collected and lost to date) is 1 million or more then the doors will open in New Game !
Did You Know? If you’re playing on a console and delete any updates (so your game is on version 1.00); you can actually skip opening the doors altogether! You need to jump off the steps onto a piece of rock, jump over the path to the left, then run forwards and jump back across to the hill on the right and finally jump towards the wall that leads to where you find the corpse holding the items. This glitch was fixed on versions 1.1 upwards.
Once the doors are open, simply run forwards and drop down the entire winding path to save time. Now run to the right and pick up the spell [Repair] and a [Large Soul of a Lost Undead] .
Turn back around and then head along the winding path. There’s a [Divine Blessing] on your left and then a bit further up you’ll find another Heide Knight who will drop his weapon the [Heide Lance] if you decide to try and kill him (he’s fast and tough by the way).
Just past the knight on the right you’ll find a [Large Soul of a Nameless Warrior + Human Effigy] . Proceed through the tunnel to reach the next area in the game: Drangleic Castle .