At the end of Act One. You'll know it because a giant yellow "Act One Complete' will flash across the screen. It'll be just after you take your first outpost in the story.
I never personally tried, but it certainly seems the game expects you to wait until it properly introduces outposts. It's not very long, I promise. You'll get there before you know it.
You now have the entire south to play with, but it'll be a long while before the northern half opens up. Also, consider using a gyrocopter to deal with the belltowers quickly and painlessly, Should be one outside that first outpost right where you meet a certain character.