고려시대 지방제도의 가장 큰 특징은 왕권에 대한 기여도에 따라 각각의 행정구역을 승격 또는 강등시키는 것이었습니다. 건국 초에는 후삼국의 통일전쟁과정에서 태조 왕건을 도왔던 지역이면 승격되었고, 후백제나 태봉(후고구려)의 편이 되었던 지역은 강등되었습니다. 후기가 되면 왜구(倭寇)의 침임을 막는데 기여한다거나, 민란(民亂)을 일으킨 책임 등을 물어 승격과 강등을 되풀이하였습니다. 김해도 예외일 수는 없었습니다. 936년에 통일을 완수한 태조는 940년에 김해소경을 김해부(金海府)로 낮추었고, 다시 임해현(臨海縣)으로 낮추었다가, 임해군(臨海郡)으로 올렸습니다. 광종22년(971)에 김해부(金海府)로 승격되었다가 지방제도가 완비되는 성종14년(995)에 10도를 정하면서 영동도의 안동도호부(安東都護府)로 크게 승격되었습니다. 목종3년(1000)에 안동대도호부(安東大都護府)가 두어졌다가, 현종3년(1012)에 금주(金州)로 고쳐 방어사(防禦使)를 두었습니다. 충선왕1년(1309)에 금주목(金州牧)으로 승격되었다가, 충선왕 3년(1311)에 김해부로 고칩니다.