시기에 따라 소재지의 변동이 있다. 고려 태조가 936년(태조 19) 후백제를 멸망시키고, 전주(全州)에 안남도호부를 설치한 것이 처음이다.
4년 뒤인 940년 다시 전주로 고쳤다. 951년(광종 2)에는 고부(古阜)에 안남도호부를 설치하였는데, 1019년(현종 10)에 다시 고부군으로 바꾸었다. 995년(성종 14)에 이와 함께 영암군에 낭주안남도호부(朗州安南都護府)를 두었는데, 이곳은 1018년에 다시 영암군으로 낮추었다.
1018년과 1019년에 고부에 설치되었던 안남도호부와 영암에 두었던 낭주안남도호부를 없앤 뒤, 1018년에 전주를 안남대도호부로 승격시켰다가, 1022년 다시 전주로 고쳤다. 1150년(의종 4)에는 수주(樹州)를 안남도호부로 삼았다.
수주는 1215년(고종 2)에 다시 계양도호부(桂陽都護府)로 고쳤으며, 1308년(충렬왕 34)에 길주목(吉州牧)으로 승격시켰다가, 1310년(충선왕 2)에 부평부(富平府)로 낮추었다.
『고려사(高麗史)』의 1272년(원종 13) 11월 기사일 기사를 보면, 삼별초가 안남도호부에 침입하여 부사 공유(孔愉)와 그의 처를 붙잡아 갔다는 내용이 있는데 이 때의 안남도호부가 수주인지의 여부는 확실하지 않다.
인종 때에 제정된 외관록(外官祿)에 따르면, 안남소도호사(安南小都護使)는 120석, 부사(副使)는 86석 10두, 판관은 40석, 법조(法曹)는 16석 10두를 받았다.