시기에 따라 소재지의 변동이 있다. 995년(성종 14)풍주(豊州)에 설치하였다가 이후 해주(海州)로 옮겼다. 『고려사(高麗史)』에서는 풍주에 설치된 도호부를 안서도호부라 하지 않지만 이 때 안동·안남·안북 도호부가 설치되었기 때문에 풍주도호부가 안서도호부로 추정된다. 해주는 본래 고구려의 내미홀(內米忽)이었는데, 신라 경덕왕이 폭지군(瀑池郡)으로 고쳤다가 고려 태조가 군의 남쪽이 바다에 임하여 있으므로, 해주라 하였다.
983년 12목의 하나였고, 995년 12주 절도사를 둘 때에는 우신책군(右神策軍)이라 하여, 양주(楊州)와 함께 좌우보(左右輔)가 되었다. 1018년(현종 9) 4도호를 둘 때, 이름을 바꾸어 해주안서도호부라 하였는데, 1122년(예종 17)에 다시 대도호부로 승격시켰다가, 그 뒤 1247년(고종 34)에 해주목이 되었다.
문종 때 제정된 외관록(外官祿)에 따르면, 안서대도호부사(安西大都護府使)는 200석, 부사(副使)는 120석, 판관은 86석10두, 사록(司錄)은 40석, 법조(法曹)는 20석을 받았다. 그리고 안서도호부의 도내 군사는 보승(保勝) 450인 정용(精勇) 874인, 1품군(一品軍) 838인 등이다.