The tower is available after Maxos, though there is a bit of stuff in between even if you don't do any sidequests (which I wouldn't recommend).
At the end of Maxos temple you can teleport to sentinel island (and back, until you reach a certain point, which you are warned about). You can mindread your first encounter there to gain a full level, so the higher level you are when you get there, the greater bonus experience points that will give you. Finishing Maxos temple almost brought me up to level 16, so I headed to the fjords to level first, rather than waste the mindread when I only needed 3k experience. I kept going, and managed to reach level 18 (for the last 4k experience, there were only level 21 imps available, which took a few tries to take out the first group).
Getting to level 18 certainly isn't required, but around level 15 or 16 you can level pretty quickly at the start of the fjords, and it is not too difficult (give your creature a mage head, or ranger if you don't have one).