Visas are an important means for countries to regulate the potential access of non-nationals to their territory. Past datasets and quantitative research on visas have focused on visa waivers, ignoring the fact that visas, where demanded, can vary greatly by cost. This paper presents a novel dataset based on a manual collection of visa costs for travel between a global set of country pairs in seven different categories (tourist, work, student, family reunification, business, transit, and other). Our analyses reveal a strong global visa cost divide that exposes the injustice in the right to travel for people located in different areas of the world. Whereas Europeans usually hardly have to work at all for travel permits, visa costs often amount to several weeks of mean income in Sub-Saharan Africa and South Asia. The result is a fundamentally paradoxical situation: The richer a country, the less its citizens pay for visas to go abroad (both in absolute terms and relative to their income). Poisson pseudo-maximum likelihood regression analyses reveal that a variety of factors influence the costs of visas between countries: reciprocal treatment, processing costs, historical-cultural ties, geographic proximity and regional, religious, economic, and political discrimination. This confirms the important role of visa costs as a tool for states to control population movements and simultaneously position themselves in international relations.