여권에 대한 가장 오래된 기록 가운데 하나는 타나크이다. 이 경전의 느헤미야서 2장 7절에서 9절까지의 기사에는 기원전 450년 경 페르시아 제국 시기 아르타세르세스 1세의 신하였던 느헤미야가 유대로 여행하겠다고 청하자 왕이 "강을 넘어서도 효력을 발휘하는" 문서를 작성하여 주었다는 내용이 적혀있다. 

중세 아랍 제국에서는 세금을 납부하였다는 것을 증명하는 영수증인 "바라아"가 여권을 대신하였다. 당시 아랍 제국에서는 시민만이 세금을 내었기 때문이다. 무슬림은 자카트를 납부하였고 딤미는 지즈야를 납부하였다. 따라서 바라아를 지니고 있다는 것은 곧 아랍 제국의 시민임을 뜻했고 여권의 역할을 하였다. 

중세 유럽에서는 항구나 도시의 성문을 통과할 때 신분증명서를 요구받았고 그것에는 소지자가 여행한 도시나 항구들의 목록이 적혀있었다. 자국의 시민이 외국을 여행하는 동안의 안전을 위해 국가가 신분을 증명하는 근대적 의미의 여권을 처음으로 시행한 사람은 잉글랜드의 헨리 5세이다. 

19세기 중반 유럽에서 기차 여행이 시작되자 이전에 비해 너무 많은 사람들이 빠른 속도로 수많은 국경을 지나가는 일이 빈번해지자 국가마다 서로 다른 이전의 여권법으로는 도저히 감당할 수 없는 지경에 이르렀고, 유럽은 보편화된 여권법을 마련하게 되었다. 

사진이 널리 전파되자 여권에도 사진을 부착하는 것이 일반화되었다. 제1차 세계대전 기간 동안 유럽의 각국은 보안상의 이유와 인력의 관리를 위해 출입국심사 절차를 만들었고, 이는 표준 절차가 되어 전쟁 이후에도 유지되었다. 한편 1920년대의 영국인들은 여권에 사진과 신체 특징을 표기하는 것을 "비인간적 처사"로 여겼다. 

1920년 국제 연맹은 여권의 발급 표준에 대한 회원국의 총의를 이끌어 내었다. 이 여권 표준은 1926년 개정되었다. 

1963년 유엔은 새로운 여권 발급 표준에 대해 토의하였으나 총의를 도출하는데 실패하였다. 그 후 1980년에 이르러 국제민간항공기구가 지원하는 가운데 새로운 여권 발급 표준에 대한 총의가 형성되었다.
중세 아랍 제국에서 여권과 세금 납부 증명서를 겸용한 서류의 이름은 무엇인가?
"바라아" 바라아