The leave tower option is a way to teleport back to where you last used a teleport to tower option. Since you have not used it outside of your tower, there is nowhere for it to take you. So yeah you will have to use the warp shrine to go to the fjords. From then on it will always take you back to the last place you used it.
