Visas are only available when the destination country is represented locally, so the concept postdates the establishment of the system of permanent diplomatic envoys in the late Middle Ages and early modern era.
Some Eurocentric details are in the German Wikipedia:
Medieval escorts are considered the forerunners of today's passports. They placed privileged travelers (diplomats, merchants, pilgrims) under the protection of the state, while destitute travelers in some regions of Germany (e.g. in the Palatinate) were seized by the princes and settled in vacant villages. The governments of the absolutist states of Europe were interested in preventing unnecessary travel by their citizens. Therefore, a passport had to be applied for each trip, the time period and itinerary specified. Population growth, impoverishment, and increasing mobility as a result of the farmer's liberation led to a significant tightening of passport and visa requirements. With the introduction of the general requirement of passports in the period between the late 18th and the first half of the 19th century, it became customary to have the documents marked by entries at the state border or previously ("visa"). Since 1813, all foreigners in Prussia needed a visa permit if they wanted to spend more than 24 hours in a community. Innkeepers were only allowed to house foreigners when such a visa had been issued, and were regarded as auxiliary organs ("non-commissioned officers") of the "aliens police".
When similar rules were adopted outside Europe, I cannot say.