I can't speak to the 1500s, but Perl-Rosenthal argues in Citizen Sailors: Becoming American in the Age of Revolution that post-revolution America issued customs forms that proved citizenship. This is kind of a crappy and reductive answer, but it is the first example I've seen in the West of anything like a passport.

In ancient China, documents were granted by the emperor.

Remember that there was a long period of time in Western culture where most people were rural, not very mobile in general, and of a class that wouldn't require travel. I think if you had money, it means someone would know someone else in your circle and you'd get a letter of introduction into another circle of aristocracy and you could just go on your name alone.