고려 후기에 양계(兩界), 즉 동북면(동계) 강릉도(江陵道)와 서북면(북계) 평양도(平壤道)에 파견된 지방관이다. 1258년(고종 45)에 쌍성총관부가 설치되면서 동계는 그 일부인 명주도(溟州道)만 남게 되었다. 이후 고려에서는 그 지역을 강릉도로 편성하고 소속 주진(州鎭)을 주현(州縣)으로 개편하였다. 그리고 강릉도에 존무사를 설치하였다.
1309년(충선왕1)에 세워진 「 삼일포매향비(三日浦埋香碑)」에 강릉도존무사가 보인다. 그보다 이른 시기부터 존무사의 설치가 이루어졌을 것이다. 1314년(충숙왕 1)에 명주에 있던 강릉도존무사의 관아를 등주(登州)로 옮겨서 북방을 진수하게 하였다. 강릉도존무사는 동북면존무사(東北面存撫使), 동계존무사(東界存撫使)라고 칭하기도 하였다. 1343년(충혜왕 후 4)에 동계존무사로 최창의(崔昌義)가 활동하고, 1374년(공민왕 23)에 이자송(李子松)이 동북면존무사로 활동하다가 면직되었다.
한편 1270년(원종 11)에 몽골이 서경에 동녕부를 설치하여 북계와 서해도를 관할하다가 1290년(충렬왕 16)에 고려에 반환하였다. 그 지역을 통치하기 위하여 존무사를 파견하였다. 1310년(충선왕 2)에 민보(閔甫)를 평양부윤 겸 존무사(平壤府尹兼存撫使)로 임명하였다. 이때 평양존무사는 평양부, 즉 서경을 중심으로 서북면을 관할하였다. 이후 평양윤을 평양도존무사(平壤道存撫使), 서북면존무사(西北面存撫使), 서경존무사(西京存撫使), 안정도존무사(安定道存撫使) 등의 명칭으로 파견하였다.
『 고려사』 백관지에 따르면 1330년(충숙왕 17)에 충혜왕이 평양도존무사를 순무사로 삼았다. 그런데 이후에도 1339년(충숙왕 후 8)에 유방세(劉方世)를 서북면존무사로 임명하고 1347년(충목왕 3)에 평양윤 윤지표(尹之彪)가 서북면존무사로 활동하였다.
한편 1318년(충숙왕 5)에 탐라에서 반란이 일어나자 배정지(裴廷芝)를 존무사로 임명하여 파견하였다. 탐라존무사는 반란을 토벌하기 위한 봉명사신의 일종이었다.
존무사는 안찰사(按察使) · 안렴사(按廉使)와 비슷한 기능을 수행하였다. 그 명칭에 있듯이 처음에는 백성을 안무(安撫)하는 임무를 맡았을 것이다. 강릉도와 평양도가 점차 남도와 같은 체제로 운영되면서 존무사의 기능은 안렴사와 거의 같았졌다. 1356년(공민왕 5) 6월에 내린 교서에 따르면 존무사와 안렴사에게 주현의 지방관을 감찰하게 하였다.
또한 1363년(공민왕 12)에도 각 도의 존무와 안렴으로 하여금 각 항목의 토지 대장을 대조하고 조세를 수납하게 하였다. 존무사는 백성의 괴로움을 묻고, 지방 관원으로 소임을 다하지 못하는 자를 살피며, 조세를 수납하는 등의 임무를 수행하였다. 한편 존무사는 쌍성총관부를 탈환할 때에 직접 작전에 참여하기도 하였다.
각 도에 파견된 존무사와 안렴사는 1390년(공양왕 2)에 도관찰출척사(都觀察黜陟使)로 바뀌었다.
평양도존무사와 강릉도존무사는 남도 안렴사와 같은 위상을 가진 지방관이었다. 몽골과의 전쟁 및 원나라의 간섭으로 서북면과 동북면의 운영 체제가 변하였다. 점차 양계의 운영 체제가 남도와 유사한 방식으로 개편되면서 존무사의 설치가 이루어졌다.