Sejarah timbulnya Paspor diperkirakan sudah sejak tahun 450 SM, salah satu referensi yang dianggap mewakili keberadaan paspor ditemukan dalam kitab suci yaitu Nehemia 2 : 7-9 disebutkan Nehemia perwakilan dari King Artaxerxes I dari Persia, memerintahkan Nehemia untuk pergi ke Yudea dan Raja memberikan sebuah surat kepada ""pemimpin diseberang sungai"" yang meminta jaminan keselamatan bagi Nehemia selama ia menjelajahi daerah tersebut.