935년(태조 18)경주에 둔 것이 처음인데, 시기에 따라 소재지의 변동이 있다. 경주는 대도독부로 승격되고 안동도호부의 위치는 상주(尙州)로 바뀌었다. 상주는 940년 상주로 불렸다가, 그 뒤에 고쳐 안동대도호부라 하였다.
983년(성종 2) 처음 12목을 둘 때에 다시 상주라 불렀다. 995년에는 김해(金海)를 금주안동도호부(金州安東都護府)로 하였는데, 이곳은 1012년(현종 3) 금주로 고쳤다. 같은 해 절도사를 폐하면서 다시 상주를 안동대도호부로 삼았다가 1014년에 상주에 안무사를 두고, 새로 경주를 안동대도호부로 삼았다.
그러나 1030년경주에 동경유수를 설치하였다. 그뒤 안동부(安東府)를 안동도호부라 하였다. 기록을 보면, 1197년(명종 27) 남적(南賊) 김삼(金三)·효심(孝心) 등이 난을 일으켰을 때, 안동부가 공이 있었다고 하여 안동도호부로 승격시켰으며, 1204년(신종 7) 동경별초(東京別抄) 패좌(悖佐) 등이 난을 일으켰을 때, 안동도호부가 공이 있었다고 하여 대도호부로 승격시켰다.
안동은 1308년(충렬왕 34)에 복주목(福州牧)으로 이름을 고쳤으며, 1361년(공민왕 10) 홍건적의 침략 때 공민왕이 이곳에 피난하여 왔는데, 복주사람이 접대하는데 공을 세웠다고 하여 다시 안동대도호부로 승격시켰다.
『고려사(高麗史)』 병지 기록을 보면 안동대도호부의 도내 주현군(州縣軍)으로 보승(保勝) 591인, 정용(精勇) 953인, 일품(一品) 1,018인을 두었다고 한다.