대도호부는 원래 중국에서 외지를 다스리기 위해 두었던 관서였다. 당나라는 고구려의 옛 땅에 9개의 도독부(都督府)를 두고, 이를 모두 거느려 다스리기 위해 평양에 안동대도호부를 설치한 바 있다.
고려 · 조선 시대 지방 행정 기구의 하나로 군사적인 요충지에 설치되었으나 점차 일반 행정 기구로 그 성격이 바뀌어갔다. 도호부(都護府)는 대도호부와 도호부의 2가지가 있는데, 고려시대의 대도호부 운영은 시기나 지역에 따라 편차가 있었다.
918년(태조 1)에 평양 대도호부(平壤大都護府)를 둔 적이 있지만, 평양이 서경(西京)으로 승격되면서 없어졌다.
안북대도호부(安北大都護府)는 983년(성종 2)에 12 목(牧)의 설치와 함께 지방 제도가 정비되면서 북계(北界) 지역의 영주(寧州)에 신설되었다. 이 명칭은 1018년(현종 9)에도 이어졌다.
안남대도호부(安南大都護府)는 1018년(현종 9)에는 전주(全州)에 설치되었다. 이후 전주는 1022년(현종 13)에 안남대도호부에서 전주목으로 변화하였다.
한편 해주에는 1018년(현종 9)에 해주안서도호부(海州安西都護府)가 설치되었다가 1122년(예종 17)에 안서 대도호부로 승격되었다. 1247년(고종 34)에 다시 해주목으로 변경되었다.
안동대도호부(安東大都護府)의 경우, 행정 사무를 맡아보는 기관이 있는 장소의 변화가 잦았다. 1012년(현종 3)에 상주에 절도사(節度使)가 폐지되면서 상주를 안동대도호부로 바꾸었다. 이후 1014년(현종 5)에 경주를 안동대도호부로 삼았다가 1030년(현종 21)에 경주를 동경 유수(留守)로 바꾸었다. 1204년(신종 7)에 안동을 안동대도호부로 삼았다. 안동은 이후 1308년(충렬왕 34)에 복주목으로 변경된 뒤 1361년(공민왕 10)에 다시 안동대도호부로 변경되었다.
고려 문종 대에 관제(官制)를 개정할 때, 대도호부의 관원으로 사(使) · 부사(副使) · 판관(判官) · 사록 겸 장서기(司錄兼掌書記) · 법조(法曹) · 의사 · 문사(文師) 각 1인씩을 두었다. 그러다가 1116년(예종 11) 판관을 통판(通判)으로 고친 뒤 관원으로 사, 판관, 사록만 두게 되었다.
조선의 대도호부 운영도 시기와 지역에 따라 변화를 겪었다. 건국 초부터 안동, 강릉, 진양 등에 대도호부를 두었다. 1392년(태조 1)에 현비(顯妃) 강씨(康氏)의 내향(內鄕)인 진양을 진양대도호부(晉陽大都護府)로 승격하였다. 이후 1402년(태종 2)에 진주목으로 환원하고 세조 때 진(鎭)을 두었다.
안변대도호부(安邊大都護府)는 1402년(태종 2)에 조사의(趙思義)의 난으로 현(縣)으로 강등되었다가 이후 다시 안변대도호부로 복구되었다.
1426년(세종 8)에 태조가 태어난 화주(和州)를 높여 영흥대도호부(永興大都護府)로 삼았다가 이후 1456년(세조 2)에 진으로 변경하였다.
1428년(세종 10)에 평안도 연산부(延山府)와 무산현(撫山縣)을 합병하여 영변대도호부(寧邊大都護府)를 설치하였다. 이후 『경국대전(經國大典)』에 안동, 강릉, 안변, 영변 4곳에 대도호부를 규정하였다.
이후 조선 후기에 대도호부는 큰 변화를 겪었다. 창원이 대도호부로 승격되었고, 영흥이 부윤에서 대도호부로 강등되었으며, 안변은 대도호부에서 도호부로 강등되었다. 그 결과 조선 후기에는 안동, 강릉, 영흥, 영변, 창원 5개 대도호부가 마련되었다.
대도호부 수령인 대도호부사는 정3품으로 부윤 · 목사와 함께 주로 문신이 임명되는 청환직(淸宦職)이었다.
『경국대전』에 대도호부는 서원(書員) 30인, 일수(日守) 40인, 외노비(外奴婢) 450명, 향교 노비 25명, 관둔전(官屯田) 20 결(結), 아록전(衙祿田) 50결, 공수전(公須田) 15결이 배정되었다. 대도호부사의 부관(副官)으로 판관을 두었으나 1894년(고종 31) 지방 제도 개혁 때 모두 폐지되었다.