Azt gondolnánk, hogy néhány száz évvel ezelőtt, amikor még nem volt még szervezett közlekedés, és a határokat sem ellenőrizték olyan szigorúan, mint manapság, nem is voltak útlevelek. De az útlevél egy meglepően ősi találmány, még a Bibliában is említik.

Nehemiás könyvében található a részlet (Nehemiás 2:7-9):

7. És mondék a királynak: Ha tetszik a királynak, adasson nékem leveleket a folyóvizen túl lakó tiszttartókhoz, hogy hagyjanak engem utazni, míg Júdába érek;

8. És adasson egy levelet Ászáfhoz, a király erdeje őréhez, hogy adjon nékem fákat gerendákul a templom várának kapuihoz, és a város kőfalához, és a házhoz, melybe költözni fogok. És megadá nékem a király, az én Istenemnek rajtam nyugvó jó kegyelme szerint.

9. És megérkezém a folyóvizen túl való tiszttartókhoz és átadám nékik a király leveleit. Bocsátott vala pedig velem a király főembereket a seregből és lovagokat.

Az első tárgyi emlékeket úti okmányokról a mongoloknál találjuk. Dzsingisz kán készíttetett néhány fémlemezt, amiket paizinak neveztek. Egyes paizikat tisztviselők vittek magukkal, hogy igazolják rangjukat és pozíciójukat, másokat utazóknak adtak, akik keresztül utaztak a hatalmas birodalmon. Általában kormányzati ügyben utazók és olyan külföldiek kapták, akik a kán védelmét élvezték.

Nagyjából tucatnyi ilyen fémlemezt találtak eddig régészek, az egyiket New York-i Metropolitani Museum of Artban állították ki. Ez  egy tibeti szerzetes nevére szól; Phagspa szerzetes Kublaj kán tanácsadója volt, a 18×11 centiméteres fémlemezt azért hordta magánál, hogy ezt bizonyítani tudja.

A következő évszázadok alatt sokszor állítottak ki ilyen leveleket, ezek voltak az első utazási okmányok, az uralkodók állították ki küldötteiknek, hogy igazolják kilétüket idegen országokban. Egy-egy ilyen okmány egyfajta védettséget is biztosított a küldötteknek, ezért nagy becsben tartották ezeket – de még nem voltak a szó mai értelmében vett útlevelek, inkább egyfajta kiváltságot jelentettek. Ráadásul nem is ismerték el zökkenőmentesen az egymás utáni kormányzatok.

A legrégebbi brit útlevelet például I. Károly király írta alá 1641-ben. De ez csak három évig volt érvényes, amíg Oliver Cromwell át nem vette a hatalmat az országban. Cromwell az összes addigi útlevelet érvénytelenítette, újakat pedig csak azoknak adott, akik felesküdtek a kormányára. Érdekes, hogy volt nyolcvan év, amikor a brit útleveleket franciául állították ki. 1772 és 1858 között a francia számított a diplomácia nyelvének, így történhetett az a furcsaság, hogy akiket Napóleon ellen küldtek harcolni, azoknak is francia nyelvű útlevelük volt.

Az első útlevelek kezelésekor nem voltak szigorú szabályok, hogy mi szerepeljen bennük, milyen képet tegyenek bele. Így voltak olyan útlevelek is, amelyek gazdái a családdal vagy kedvenc háziállatukkal pózoltak, természetesen a legszebb, legdivatosabb ruháikban. Először 1835-ben javasolták, hogy néhány fizikai jellemzőt is írjanak az útlevél tulajdonosáról, mint például magasságát, szeme színét. De ezt a javaslatot felháborodva elutasították azzal az indokkal, hogy ez degradáló és offenzív (erről bővebben itt írtunk korábban). Csak az első világháború környékén kerültek ezek az információk az útlevelekbe.