나말여초의 혼란기를 수습한 고려는 각 지방에 존재하는 호족세력을 통제하기 위해 지방제도를 정비함과 아울러 행정구역도 새롭게 재편하였다. 고려시대의 부산에 관한 기록인『고려사』지리지에는, "동래현은 본래 신라의 거칠산군으로 경덕왕이 동래군으로 고쳤는데, 현종 9년 울주에 내속되었고, 뒤에 현령을 두었다. 온천이 있다"라 하였고, 또한 "동평현은 본래 신라의 대증현이며, 경덕왕이 지금 이름으로 고쳐 동래군의 영현으로 삼았고, 고려 현종 9년(1018) 에 양주에 내속 되었다. 절영도가 있다"라고 기록되어 있다.
『신증동국여지승람(1530)』동래현조에 의하면, "고지도(古知道) 부곡은 즉 고지섬을 말한다고 하였고, 조정부곡은 동평현의 북쪽 20리에 있다고 하였으며, 형변(兄邊)부곡은 동평현의 남쪽 해안에 있으며, 신라가 남해신을 여기에서 제사하였는데 중사(中祀=나라에서 지내던 제사)의 기록에 실려 있다고 하였다. 부산부곡(富山部曲)은 부산이라고 하였다. 그리고 여기에 이어서 생천향(生川鄕)은 동평현의 남쪽 20리에 있다"라고 하여 4개의 부곡과 1개의 향이 존재하였다고 기록되어 있다.
따라서 부산(동래)은 고려시대 동래현, 동평현으로 존재하였다고 볼 수 있다. 그리고 동래온천은 고려시대에도 널리 알려져 그 온도는 달걀도 익힐 수 있는 정도이며, 병을 가진 사람도 목욕만 하면 낫는다고 전할만큼 유명하였다. 또 당시 지식인이었던 이규보 등도 동래 온천을 찬양하는 시(詩)를 지었다. 이는 고려시대에 동래 온천이 사람들에게 널리 알려졌다는 증거이다. 또 앞에서 언급하였던 것처럼 절영도가 목장으로서 이름을 널리 알렸던 것으로 보인다. 특히 후삼국 중에서 서로 자웅을 다투던 후백제의 견훤이 부산의 절영도 명마 한 필을 고려 태조 왕건에게 선물하였다는 고사는 유명하다.
고려말 부산은 왜구가 침입하여 노략질이 심하여 피해가 가장 심하였던 곳으로, 왜구의 활동 범위는 광대하였는데, 그 중에서도 특히 많은 피해를 입은 곳이 우리나라 남쪽의 해안지방이었다. 공민왕 때 경남, 부산지방에 있었던 약 30회에 걸친 왜구의 침략은 부산지방의 사정을 단적으로 보여준다.
이와 같은 정세 아래서 조정에서는 회유와 토벌의 강온정책을 펼쳐 이를 격퇴하고, 일본에 사신을 보내 왜구의 금지를 요청하는 동시에 해변의 주요지역의 군·현에 성보(城堡)를 설치하라는 명령을 내리게 되었다. 이에 경상도 도순문사(慶尙道都巡門使) 박위는 우왕 13년(1387)에 종래 황폐하였던 동래읍성을 개축하게 되었다. 이때 쌓은 육성은 석축인데 둘레가 3,090보, 높이가 13척에 달하는 것이었다.