Indeed. For thousands of years people were able to move about relatively freely in most parts of the world, exceptions most often due to war. Only relatively recently has it become the norm to need permission from multiple states to move between them. Prior to the U.S. Civil War, it was difficult to even determine who someone was if they left their area of birth. Most forms of identity were informal and ultimately relied on a community attesting to who someone is. Identity systems weren't formalized and reliable, so you could start a new life in a new place under a new identity if you wanted to.
While state-enforced identity controls are used to enforce travel controls, it need not be so. You only need identity controls for state sponsored benefits (insurance, welfare, licensure, etc). There is no necessity for your mobility to be imparied by those identity controls; it is only how states have chosen to do it.
My point was that identity controls predated travel controls and were a prerequisite for a "papers please" kind of society. Each state chooses (either directly or by will of its voters) what responsibilities it owes to non-citizens in its territory. Those responsibilities can range from almost nonexistent to very generous, but it is ultimately the choice of the state, and not the visitors to that state.
