1369년(공민왕 18)에 원과의 관계 단절을 위한 동녕부(東寧府) 정벌을 앞두고 국경의 군사요지인 서경(西京)·안주(安州)·의주(義州)·이성(泥城)·강계 등에 만호부를 설치하였다. 강계는 1361년(공민왕 10)에 독로강만호(禿魯江萬戶)라 칭하다가 1369년에 만호부로 개명한 것이다. 만호부가 설치된 강계·이성 등은 납합출(納哈出), 고가노(高家奴) 등 여진이 자주 침입하는 지역이었다. 만호부는 몇 개의 군(軍) 또는 익(翼)으로 구성되었는데 강계만호부는 진변(鎭邊), 진성(鎭城), 진안(鎭安), 진영(鎭寧) 등 4군으로 구성되었다.
만호부 제도는 원의 제도를 받아들인 것이지만 기본적으로는 군사·행정상의 요지인 큰 주(州)를 중심으로 그 주변에 있는 주·현(州縣)을 이에 예속시킨 고려 전기의 분도제(分道制)와 유사한 방어체제였다. 만호부의 지휘체계는 상만호(上萬戶)·만호(萬戶)·부만호(副萬戶) 등의 상급 지휘부와 익의 지휘자인 천호(千戶), 그리고 하급지휘관인 백호(百戶)·통주(統主) 등으로 이루어졌다. 상급지휘관인 만호는 중앙의 고관 중에서 지방 사정에 밝은 지방 출신자가 임명되었고 천호 이하 하급 지휘관은 토착세력가들로 임명되었다. 만호부를 구성하는 익군(翼軍)은 병농일치(兵農一致)의 군대로서 모든 장정이 익군조직에 소속되어 평상시에는 농경에 종사하다 유사시에는 모두 동원되었다.
이후 조선왕조에 들어와 1403년(조선 태종 3) 강계부(江界府)로 고쳤다. 1423년(태종 13)에 다시 강계도호부(江界都護府)로 개명되었다.