Istilah paspor sendiri berasal berasal dari Sea Port (pelabuhan laut). Di Eropa abad pertengahan, dokumen itu dikeluarkan bagi pelancong oleh penguasa setempat, dan biasannya berisi daftar kota di mana pemilik dokumen diijinkan lewat.