В Исламском Халифате паспортом служил чек об уплате специальных налогов: закят для мусульман или джизья для немусульман. Таким образом, путешествовать в другие районы Халифата разрешалось только послушным налогоплательщикам. В принципе аналогичная система применяется во многих современных странах, в том числе в России, когда должникам ограничивают выезд за границу по решению суда или отзывают паспорт.
Обычно считается, что слово «паспорт» итальянского или французского происхождения и обозначает старинный документ для прохода через морской порт. На самом деле точнее говорить, что это документ для прохода через дверь или ворота в городской стене, так как французское слово porte означает именно дверь. В Средневековой Европе подобные документы выдавались путешественникам местными властями, и обычно содержали список городов и поселков, в которые обладателю такого паспорта разрешался въезд. Аналогичная система до сих пор сохранилась в системе российских виз, выдаваемых иностранным гостям, где имеется поле с перечислением городов, куда путешественник намеревался ехать. В Средние века для прохода в порт документы не требовались, поскольку порт был открытой зоной для торговли, однако паспорт требовался для путешествия по земле и проникновения в города через городские стены и заставы.
В России, согласно Соборному уложению 1649 года, аналогом загранпаспорта служила «проезжая грамота». Для поездки в «иное государство» подданым требовалось «бить челом государю … (или) воеводам о проезжей грамоте»; в обязанности воевод входило выдавать эти проезжие грамоты «безо всякого задержания».
До начала 20 века паспорта содержали только текстовые поля с перечислением антропометрических данных обладателя, позднее с распространением фототехнологии стала обязательной фотография владельца.
В конце 19 века и до начала Первой Мировой Войны паспорт не требовался для путешествий по Европе и пересечение границ было простым. Поэтому довольно мало людей имели паспорта. Слом паспортной системы в начале 20 века в Европе был результатом развитого железнодорожного движения. Железнодорожная система, резко выросшая в середине 19 века, позволяла перемещаться быстро огромному количеству пассажиров, и пересекала множество границ. Это сделало традиционную паспортную систему в Европе слишком сложной и от нее пришлось отказаться. В Османской империи и в царской России паспортная система сохранилась в дополнение к системе внутренних паспортов, контролирующих передвижение внутри страны.
Во время Первой Мировой войны правительства европейских стран усилили пограничный контроль в целях безопасности (защиты от шпионажа) и для управления миграционными потоками квалифицированной рабочей силы. Такое управление сохранилось после Второй Мировой войны и стало рутинной процедурой. Известно, что британские туристы 1920ых сетовали на «недемократическую» процедуру, особо много жалоб выпадало на требование фотографий и антропометрические данные.
В 1920 году Лига Наций провела специальную конференцию по паспортам и проездным документам. Принципы паспортной системы были определены также на следующих конференциях в 1926 и 1927 годах.
ООН провела аналогичную конференцию в 1963 году, но об основных принципах глобальной
паспортной системы договориться не удалось. В начале 1980ых под покровительством
ИКАО такие рекомендации были, в основном, приняты. Например, в них был утвержден
полиграфический формат современного паспорта — то что это многостраничный буклет
размером 88.0 х 125.0 мм.