When did the modern visa system become widespread?

These things come and go, as convenience and fear vie for attention in the public consciousness. I will extend to question to include passports, as there is an essential link between passports and visas, though they have somewhat different functions.

Passports are essentially identity documents and general requests for safe travel from the government of the holder's country to the government of the place of travel.

Visas are specific permissions to stay in a particular country and are used to more finely control what a person can do when travelling, exclude particular groups (e.g. criminals, certain nationalities) and to raise revenue. Visa requirements and costs are determined by security concerns, political expediency, trade agreements, and sometimes in a tit-for-tat manner.

Passports

In The Economic Consequences of the Peace, Keynes claims that is was the onset of World War I that borders began to be rigorously controlled, and documents began to be required for transit in modern Europe.

Chapter II, Europe before the War:

He could secure forthwith, if he wished it, cheap and comfortable means of transit to any country or climate without passport or other formality, could despatch his servant to the neighboring office of a bank for such supply of the precious metals as might seem convenient, and could then proceed abroad to foreign quarters, without knowledge of their religion, language, or customs, bearing coined wealth upon his person, and would consider himself greatly aggrieved and much surprised at the least interference.

Passport standards were defined in two conferences organised by the League of Nations, one in Paris in 1920 and another in Geneva in 1926.

It is important to note that nations and the boundaries were significantly reconfigured in the aftermath of WWI and that enforcement of new boundaries would have helped define and legitimise these new entities to some extent.

The Government of Canada affirms this point, but also states that passports and visa were common for travel in Europe, but the advent of rail travel made checking such documents infeasible and they were phased out in the mid to late 19th Century, before being reinstated for security reasons from WWI in what was seen as a temporary measure.

The rising popularity of rail travel in the mid-19th century led to an explosion of tourism throughout Europe and caused a complete breakdown in the European passport and visa system. In answer to the crisis, France abolished passports and visas in 1861. Other European countries followed suit, and by 1914, passport requirements had been eliminated practically everywhere in Europe. However, World War I brought renewed concerns for international security, and passports and visas were again required, as a "temporary" measure.

It also states that visa and passport free travel was possible between Canada and the US until the American Civil War.

Before 1862, Canadians, as British subjects, could travel freely to and from the United States without passports.

During the American Civil War, however, authorities in the United States wanted more reliable certification from people living in Canada. In 1862, the Governor General, Viscount Monck, introduced a centralized system for issuing passports.

These two examples show that after engaging populations in total war, border controls become strengthened.

After World War II, in 1947, the regulation of passports was given to the International Civil Aviation Organization (ICAO), an agency of the United Nations.

Visas

Visas are more complicated and may be required for entry and/or exit to a particular country or for particular purposes (e.g. work or leisure travel). The rules governing them are essentially a bell-weather of the relations between states. Indeed, friendly nations often participate in visa-free arrangements, particularly for tourist travel. Such arrangements have been developed at different points in time.

Many nations also operate a visa-on-arrival policy (essentially just a requirement for payment), though it may depend on citizenship.

As with the aftermath of WWI, the aftermath of WWII and up until the 1960's, was a time of great upheaval as empires crumbled and nations found their independence, particularly in Africa.

Malcolm X

It is not clear that Malcolm X was free to enter Saudi Arabia without a visa in normal circumstances. Indeed, his wikipedia article states that he had significant trouble entering and after some time entered as a state guest rather than a regular traveller.