From the History of Passports page on the Canadian government website:
Posted on November 14, 2004 09:28 PM. Filed under: history & archaeology.One of the earliest mentions of passports dates back to about 450 BC. Nehemiah, an official serving King Artaxerxes of ancient Persia, asked permission to travel to Judah. The King agreed and gave Nehemiah a letter "to the governors of the province beyond the river", requesting safe passage as he travelled through their lands.
Today's Canadian passports still carry such a letter of request. Inside the front cover is a letter issued in the name of Her Majesty the Queen. Like Nehemiah's letter, this also requests safe passage and protection for the bearer.
Not until the reign of King Louis XIV of France did these "letters of request" become popular. The King granted personally signed documents to his court favourites. The letter was dubbed "passe port", literally meaning "to pass through a port", because most international travel was by sailing ships. Hence the term "passport".
Within 100 years of Louis XIV's reign, almost every country in Europe had set up a system to issue passports. Besides needing passports from their own countries, travellers also had to have visas issued by the countries they wanted to visit, much as we have travel visas today.
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. [continue]