釜山で最も古い人類の痕跡は, 海雲台区佐洞•中洞遺跡から発見されている。これらの遺跡では約1万5千年から2万年前のものと推定される石斧•礫器(れっき)•削器(さっき)•掻器(そうき)•石刃(せきじん)など, 様々な打製石器が出土しており, 少なくとも後期旧石器時代から人類が釜山で暮らし始めたことを示している。
今から約7千年から8千年前の新石器時代の人類は, 食料資源が豊富な海辺に集まって生活し, 住居址と墓, 貝塚を残した。影島区東三洞の貝塚と江西区凡方遺跡から出土した櫛目文(くしめもん)土器, 道具の発達を示す磨製石斧や釣り針, 貝釧, 骨で作られた耳飾りなどが展示されている。また, 貝塚で出土した各種の魚類, 鹿やイノシシなどの動物の骨から当時の食生活がうかがえる。この他にも, 海を渡って日本との交流があったことを示す黒曜石, 縄文土器をはじめ, 新石器時代の埋蔵文化がよく反映されている加徳島•獐項遺跡の資料も展示されている。
約3千年前に釜山地域で暮らしていた青銅器時代の人類は, 河川の周辺や低い丘陵地帯で農耕を基盤に生活した。東萊区温泉洞, 金井区老圃洞の住居址をはじめ, 江西区美音洞, 蓮堤区社稷洞の支石墓で出土した赤色磨研土器, 石刀, 石鏃(せきぞく：やじり), 半月形石刀, 石鑿(いしのみ)などから本格的な農耕生活の様子と階層の発生など青銅器時代の文化がうかがえる。
青銅器時代の後半頃に鉄器文化が流入され, 釜山地域にも弁韓12カ国の一つである瀆盧国が形成された。灰色の瓦質土器のような新しい土器と木槨墓が登場したほか, 鉄で作られた鉄剣, 鏃, 斧など多様な道具と武器が広く使用されるようになった。
鉄器の使用が一般化され, 戦争が頻繁に起きた激動期になると, 三韓の小国は隣接する小国と統合しながら徐々に古代国家として成長していく。釜山の瀆盧国は, 4世紀代の金海の金官国と密接な関係を結びながら成長する。しかし5世紀以降になると, 新羅が進出して新羅文化が定着する。東萊区福泉洞古墳群と蓮堤区蓮山洞古墳群で出土した墓, 金銅冠, 馬具, 鎧, 器台など各種の遺物から文化激変期にあった釜山の姿がよくうかがえる。
三国を統一した新羅は, 中央集権的な統治を目的に685年（神文王5年）に地方制度を改編し, 地方の郡県に中央の管理を派遣する郡県制を実施する。釜山は757年（景徳王16年）に梁州（今の梁山）の東莱郡に編制され, 東萊という漢字名を使用するようになった。この時期には仏教文化が大流行し, 仏式の葬儀文化である火葬が全国的に盛んに行われた。また, 全国で大小の寺院が建てられ, 釜山地域にも華厳十刹の一つである梵魚寺(ポモサ)と長安寺(チャンアンサ)が創建された。
高麗は後三国統一後, 地方行政区域を整備した際, 釜山地域の格を下げて統一新羅時代にすでに地方官が派遣されていた主県の東莱郡を蔚州（蔚山）の属県に編制し, 東莱郡の属県であった機張県と東平県は梁州（梁山）の属県とした。この時期の釜山の姿は, 東莱古邑城と楽民洞遺跡などで出土した瓦と, 北区德川洞の墳墓遺跡で出土した青磁, 菉山洞青磁窯址で出土した緑靑磁などから垣間見ることができる。
三国を統一した新羅は, 中央集権的な統治を目的に685年（神文王5年）に地方制度を改編し, 州郡県制を実施することになる。地方制度が整備されるに従い, 社会雰囲気が統一以前とは大きく異なってきた。
統一新羅の端の地域となった釜山は, ヤンジュ（良, 梁州。現在の梁山）の東萊郡として編制され, 751年（景徳王16年）に東萊という漢文式の名前が使われるようになった。釜山と関連した話としては, 新羅王らが何度も東萊温泉を訪れたという記録や眞聖女王に政治改革を建議したものの頓挫した崔致遠が海雲台に来て過ごしたという話などが伝わっている。この時期, 仏教の普及によって釜山にも梵魚寺が建立され, 現在３層の石塔と石灯が残っている。 華厳十刹の一つである梵魚寺は, 678年（文武王18年）金井山に最初に建立されたと伝えられており, 830年（興徳王10年）に営繕されたといわれている。釜山に残っている統一新羅遺跡は, 土器窯など日常生活と関連したものが多く, 瓦造りの建物が最初に建てられた場所でもある。
高麗（913～1392）の後三国統一以降, 釜山は政治の中心から遠い地域となり, 高麗初期には蔚山, 梁山など周辺の地域に比べても相対的に劣悪な条件にさらされていた。 統一新羅の時期に既に地方官が派遣される州県であった東萊郡は, 高麗初頭その地位を喪失し, 1018年（顕宗9年）には蔚州（蔚山）の属県に編制され, 東萊郡の属県であった機張県と東平県はそれぞれ蔚州 と梁州（梁山）の属県となった。
しかし, 高麗中期以降, 東萊地域の土着勢力である鄭氏一族, その中でも特に毅宗王の時代, 鄭瓜亭曲を建てたことで有名な鄭敍のような比重のある人物を輩出するなど, 釜山地方は徐々に政治的除外から抜け出すようになった。 また、釜山地方は海岸と大きな川を挟んでいる地理的条件により, 対蒙抗争期や三別抄抗争期, 西•南海岸の倭寇の跋扈時期を経て, 次第にその重要性が明らかになり, それ以降朝鮮時代には倭との通交のための関門として歴史の前面に登場するようになる。