Паспорт - "проход через ворота"

Само слово паспорт произошло от итал. passa porto (фр. "passe port") - проход через ворота. Средневековый город имел несколько ворот в городских стенах, разрешение на проход через эти ворота и называлось passa porto. 

В России первый паспорт появился при Петре I.

В 30-х гг. и до конца XIX в. «Устав о паспортных и беглых» обязывал всех лиц предъявлять паспорта при переезде из одной губернии в другую на установленных в городах заставах, а по прибытии на место - полиции. 
С 1883 г. домохозяева непременно должны были извещать полицию обо всех прибывших и выбывших во всех городах, посадах и местечках, представляя в полицию их паспорта для регистрации.

Так что путешествие без паспорта по Российской империи было невозможно.