원나라는 피지배층을 군호(軍戶)와 민호(民戶) 등 직역에 따라 여러 그룹으로 나누어 관할하였다. 북방의 유목 민족들은 공통적으로 십진법 단위에 따라 인호(人戶)를 편제하였는데, 이 가운데 만호(萬戶) · 천호(千戶) · 백호(百戶) 등은 군대의 단위이면서 동시에 군호를 관할하는 단위이기도 하였다. 원나라에서 고려인에게 만호부의 관직을 수여한 사례는 1258년(고종 45)에 조휘(趙暉)와 탁청(卓靑)이 화주(和州) 이북을 들어 몽골 제국에 항복했을 때, 탁청에게 천호를 제수한 사례가 최초이다. 이듬해 최의(崔竩)의 제거 사실을 알린 사신 박희실(朴希實)과 조문주(趙文柱)는 처음으로 만호를 제수받았다. 그러나 이때까지의 만호, 천호 등 군직의 수여는 일회적인 일이었다. 고려에서 만호 직책의 수여가 본격화된 것은 1280년(충렬왕 6)의 제2차 일본 원정이 계기가 되었다. 이때 원나라 세조(世祖)는 충렬왕의 요청에 따라 김주정(金周鼎) · 박구(朴球)에게 만호를, 박지량(朴之亮) 등 10인에게 천호를, 조변(趙抃) 등 30인에게 총파(總把)를 수여하였다. 만호부가 고려에 처음 설치된 것은 일본 정벌의 실패 직후인 1281년이었다. 이때 일본의 보복 공격에 대비해 김주(金州 : 지금의 경상남도 김해) · 합포(合浦 : 지금의 경상남도 창원) · 고성(固城) 등 남해안 요충지에 ‘김주 등처 진변만호부(金州等處鎭邊萬戶府)’를 설치하였다. 이후 합포등처진변만호부(合浦等處鎭邊萬戶府: 合浦萬戶府)로 바뀌었다. 이어서 충렬왕 때에 지방인 전라도와 서경(西京)에 전라도진변만호부(全羅道鎭邊萬戶府)와 서경등처관수수군만호부(西京等處管水手軍萬戶府)가 각각 설치되었으며, 1293년(충렬왕 19) 전후에는 수도 개성의 치안 유지를 위해 순군만호부(巡軍萬戶府)가 설치되었다. 그리고 1301년(충렬왕 27)에는 기존의 탐라총관부(耽羅摠管府)를 대신하여 탐라만호부(耽羅萬戶府)가 설치되었다.
직제는 원나라의 만호부와 같이 도만호(都萬戶) · 도부만호(都副萬戶) · 만호 · 총관(總管) · 부만호 · 총파(摠把) · 천호 · 탄압(彈壓) 등으로 구성되었을 것이나, 실제로는 만호 · 부만호 · 천호에 임명된 사례만 있다. 만호부의 관직은 원칙적으로 원나라가 직접 수여하였다. 따라서 만호는 황제 명의의 관직 임명장인 선명(宣命)이나 그 권위를 상징하는 패부(牌符)를 수여받았다. 또한 만호의 직위는 세습되는 것이 일반적이었는데, 김방경(金方慶) · 김흔(金忻), 나유(羅裕) · 나익희(羅益禧), 김주정 · 김심(金深), 권준(權準) · 권겸(權謙), 조인규(趙仁規) · 조연수(趙延壽) · 조충신(趙忠臣) 등의 사례가 보인다. 다만 정동행성(征東行省)의 관직이 그러했던 것처럼 만호부의 관직 역시 고려 왕이 추천해서 원으로부터 형식적인 임명 절차를 밟기도 하였다. 대체로 만호부 설치 초기에는 국왕의 영향력이 강했으나, 충렬왕 복위 연간 이후로는 왕권과 대립하는 양상도 자주 보였다. 만호부는 기본적으로 국방과 치안을 담당했다. 1282년(충렬왕 8)까지도 김주 등에 원나라 군대의 주둔 사실이 확인되나 이후 점차 철수하였다. 시간이 지남에 따라 만호부는 군사적 기능 이외에도 해당 지역에서의 민정에도 개입하는 일이 많아졌다. 1356년(공민왕 5)의 개혁 조치로 만호부의 성격이 크게 변하였다. 공민왕은 기존에 설치된 5개의 만호부 이외에는 모두 철폐할 것을 요구하였다. 실제 철폐 여부는 자세히 확인되지 않으나, 기존과 같이 만호부 운영, 만호직 임명에 원나라의 영향력이 축소되었음은 분명하다. 이후 고려 정부는 원나라와는 무관하게 군사 제도의 일환으로서, 만호 · 천호 등으로 이어지는 군사 조직을 운영하였다. 1369년(공민왕 18)에는 동녕부(東寧府)를 공격하기에 앞서 서북면(西北面)에 5개의 만호부를 새로 설치하기도 하였다. 또한 1372년(공민왕 21)에도 북청(北靑)에, 1390년(공양왕 2)과 1391년(공양왕 3)에는 각각 길주(吉州)와 갑산(甲山)에 만호부를 설치하는 등, 고려말까지 국경 지역에 10개의 만호부를 두었다. 한편 공민왕 때에는 왜구를 막기 위해 강화만호(江華萬戶) · 왜인추포만호(倭人追捕萬戶) 등이 임명되었다. 1374년에는 수군(水軍)이 창설되면서 도만호 · 만호 · 부만호 등의 직제가 마련되었다. 그리고 1388년(우왕 14)에 조준(趙浚) 등의 건의에 따라 왜구 방어를 위한 수군만호부(水軍萬戶府)가 설치되었다. 조선 건국 이후 만호부는 모두 폐지된 듯하나, 만호만이 그대로 남아 서반(西班)의 외관직으로 사용되었다. 품질(品秩)은 조선 초의 3품 이상에서 1413년(태종 3)에 3품으로 개편되었고, 뒤에 종4품으로 되었다. 이들은 주로 연변의 요충지에서 상류군(常留軍) 또는 병선을 관장하고 외적에 대비하는 임무를 맡았다. 조선시대에 영안도(永安道) · 평안도에 두었던 병마만호와 수군 제진(諸鎭)에 두었던 수군만호는 고려 말 서북면 지역의 만호부들과 왜구 방비를 위한 수군만호부에서 각각 유래하는 것으로 볼 수 있다.