일명 선병도부서(船兵都部署)라 불렸다. 고려 전기 해안의 방어를 위한 수군전담관서로서 동북양계(東北兩界)의 도부서(都部署)와 동남해도부서(東南海都部署)가 있었다.
도부서의 설치시기 및 기능에 있어서는 다소 차이가 있다.
동계방면에는 대략 1005년(목종 8)∼1009년(현종 즉위년) 사이에 진명도부서(鎭溟都部署 : 지금의 함경남도 원산 부근)가, 1044년(정종 10)∼1049년(문종 3) 사이에 원흥도부서(元興都部署 : 지금의 함경남도 정평)가 설치되어, 당시 빈번하게 동해안을 침범하던 동여진(東女眞)의 해적에 대비하였다.
그리고 북계방면에는 통주도부서(通州都部署 : 지금의 평안북도 선천)와 압강도부서(鴨江都部署 : 지금의 압록강 남안)가 있었다.
대략 996년(성종 15)∼1019년(현종 10)에 설치된 통주도부서와 994년(성종 13)∼1039년(정종 5)에 설치된 압강도부서는 그 설치목적이 동계도부서와 같이 해적의 침입에 대비했다기보다는 주변의 도(渡)나 진(津)의 방어 및 군사요충지의 지상군 지원에 있었다.
직제는 고려의 전면적인 관제개혁이 실시된 문종 이전에는 중국 5대와 송(宋)·요(遼) 등에서와 같이 도부서·부부서(副部署)·판관 등의 직관명이 사용되었다. 그러나 이 후에는 도부서사(都部署使, 6품)·도부서부사(都部署副使, 7품)·도부서판관(都部署判官) 등 다분히 고려 특유의 직관명으로 개칭되었다.
이들은 모두 동계와 북계의 병마사(兵馬使)의 지휘·감독을 받으며 일선 전투수군線戰鬪水軍)으로서의 기능과 임무를 수행하였다.
그리고 경상도·전라도·양광도 등의 연해지역을 관장하는 선병도부서로서 동남해도부서(東南海都部署)가 있었다. 그 설치시기는 대략 1049년 이전으로 추정된다. 이 동남해도부서 역시 본질적으로는 수군을 통수(統帥)하여 해상으로부터의 침입에 대처하는 것이었다.
그러나 양계도부서와 같이 일선전투수군이라기보다는, 동남해 방면을 관할해역으로 하는 후방경비수군으로 주로 비군사적 임무인 일본으로부터의 방물진공(方物進貢)과 표류민 호송을 위한 사신의 응대 등 국가 간의 공식적인 교섭을 보조하는 임무를 수행하였다.
때로는 안찰사(安察使)·안렴사(安廉使)와 마찬가지로 지방의 뇌옥(牢獄)의 검찰과 지방관의 감독 등 지방행정적 임무를 수행하기도 하였다.
이러한 기능상의 이유로 그 본영의 소재지가 원래 경주였던 것이 일본과의 교섭을 위한 교통상의 문제를 감안해 김해로 바뀌게 되었다. 명칭에 있어서도 안찰사의 이칭(異稱)으로 이해되기도 하였다. 그 직제는 양계도부서와 같으나 동남해도부서사의 품계가 5품으로 양계도부서사보다 높다.
이와 같이, 고려 전기 해상의 경비 및 방어, 그리고 내왕외인(來往外人) 및 외선(外船)의 조처 등에 관한 임무를 수행한 도부서는 문헌상 1390년(공양왕 2) 혁파되고 대신 사수서(司水署, 또는 司水寺)로 개칭되었다고 한다.
그러나 실질적으로는 이미 1107년(예종 2)윤관(尹瓘)의 여진정벌과 9성의 축조 및 반환에 의해 동여진과의 분쟁이 종식됨에 따라 그 존재의의가 상대적으로 약화되고, 무신정권기의 병제개편 때 본질적인 변동을 겪게 된 것으로 보인다.
1186년(명종 16)을 끝으로 도부서는 기록에 보이지 않게 되고, 충선왕 때 도부서를 당시 어량천택(魚梁川澤)을 관장하는 도진사(都津司)의 관할 하에 두었다는 기록이 보인다. 이는 고려 후기에 이르면 수군전담기관으로서의 도부서의 본질이 이미 상실되었음을 증명해준다.