Travel rights are found as early as the Magna Carta:
It shall be lawful to any person, for the future, to go out of our kingdom, and to return, safely and securely, by land or by water, saving his allegiance to us, unless it be in time of war, for some short space, for the common good of the kingdom: excepting prisoners and outlaws, according to the laws of the land, and of the people of the nation at war against us, and Merchants who shall be treated as it is said above.The Articles of Confederation, the first constitution of the United States, expressly protected the right to "free ingress and regress to and from any other State."
These rights of travel, as with a large variety of other traditional rights, were incorporated into the Constitution via the Fifth Amendment Due Process Clause and the Ninth Amendment Unenumerated Rights Clause. Rights of travel were recognized in the 1999 case Saenz v. Roe.
During the struggle for freedom in Eastern Europe, the Soviet Union and their puppet communist governments turned their states into vast prisons by restricting freedom to leave their countries. The Berlin Wall was a highly visible but small part of this effort. Many died in their efforts to defect to the free West. Thus reisen freiheit (freedom of travel) became a key demand of those seeking freedom from these prison states, and when freedom of travel became possible these states fell. Restrictions and burdens on the right to leave a country are key symptoms that said country is no longer free.