갑주는 본래 허천부(虛川府)로서 오랫동안 여진의 점거하에 있었고, 또한 여러 차례 전란을 겪어 황폐한 지역이었다. 1391년(공양왕 3)에 비로소 갑주(甲州)라고 부르고 만호부를 두었다. 우왕대에 변방의 방위를 맡고 있던 이성계(李成桂)가 여진(女眞)·달달(達達)·요심(遼瀋) 등과 인접한 요해지로서 자주 이민족의 침략을 당하는 아오(我吾)·읍초(邑草)·갑주(甲州)·해양(海陽) 등 변경에 대한 방위 대책을 건의한 바 있었다. 바로 그러한 배경하에서 갑주에 만호부가 설치된 것으로 보인다.
갑주만호부(甲州萬戶府) 역시 다른 만호부와 마찬가지로 갑주를 중심으로 그 주변에 있는 주·현(州縣)을 이에 예속시켜 방어체제를 편성하였을 것이다. 만호부의 지휘체계는 상만호(上萬戶)·만호(萬戶)·부만호(副萬戶) 등의 상급 지휘부와 익(翼)의 지휘자인 천호(千戶), 그리고 하급지휘관인 백호(百戶)·통주(統主) 등으로 구성되었다. 상급 지휘관인 만호는 중앙의 고관 중에서 지방 사정에 밝은 지방 출신자가 임명되었고 천호 이하 하급 지휘관은 토착세력가들로 임명되었다. 만호부를 구성하는 익군(翼軍)은 병농일치(兵農一致)의 군대로서 모든 장정이 익군조직에 소속되어 평상시에는 농경에 종사하다 유사시에는 모두 동원되었다.
1413년(태종 13)에 갑산군(甲山郡)으로 고쳐졌고 1437년(세종 19)에 진(鎭)을 설치하고 첨절제사(僉節制使)를 두었다. 1461년(세조 7)에 갑산도호부(甲山都護府)로 승격되었다.