Comment by nl

For identity away from people that knew you or your relatives you had to rely on physical letters of introduction from trusted, well know people.

But usually you were proving that you were entering (or leaving) for a legitimate purpose rather than identity exactly. There is a long history of travel documents for this, see https://en.wikipedia.org/wiki/Passport#Antecedents

Worth noting that once urban centers formed travel became the exception rather than the rule. There were traders who traveled trade routes and knew that requirements on those routes but for more exceptional travel you had to rely on these introductory letters in many areas of the world.

Mass migration events were different of course - and were always problematic.