* When you start, there might be events in place that renders fast travel inaccessible. Talking about striders, boats etc, not point & click travel.
* Once you reach a certain point in the main quest, and/or side quests, fast travel becomes accessible.
* Do a certain side quest for a good reward, but it also makes fast travel inaccessible for a while or until a certain condition is met.
* Later on, fast travel is again accessible. Maybe point & click travel is even invented, with some kind of story to back it up.
So, not only rewards, but also negative consequences you might not see immediately.
Another example is evolving gameplay:
* At the start, you have to do a bunch of complex tasks manually. Like, you're not a hunter, so you have to hunt for food, prep your campsite or whatever.
* Later on, you can automate these tedious tasks because you have the skill (if you went that route). Multiple approaches might be cool too.
Stuff like this causes the gameplay to be more varied over time, and at the same time you get to eventually automate processes that are only fun for so long. When something becomes tedious, it takes away a great deal of immersion from the game.
But no "You're now level 20, so you can fast travel anywhere". There needs to be a story, whatever story, behind it.