Melanezija pirmą kartą buvo apgyvendinta prieš maždaug 50000 metų. Kadangi regiono dabartinė rasinė sudėtis labai mišri, spėjama, kad senieji gyventojai čia kėlėsi per kelias bangas, tapdami dabartinių negritų, papuasų protėviai.
Austroneziečiai atsikėlė į šias žemes vėliau, maždaug 1500 m. pr. m. e., austroneziečių migracijos laikais. Šie žmonės, apsigyvenę Melanezijoje, žinomi Lapita vardu. Lapitos atstovai buvo keramikos gamintojai, gerai įgūdę jūrininkai bei žemdirbiai, naujai apgyvendinę visą Melaneziją. Jie pakeitė vietos gyventojų tautinę sudėtį, suformuodami melaneziečių tautas ir kalbas.
Tik Naujoji Gvinėja liko gyvenama senųjų gyventojų.
Dėl specifinių vietos gamtinių sąlygų Melanezijoje nesusiformavo aukštesnio lygio kultūra. Regionas išliko akmens amžiuje. Vieninteliai archeologiniai paminklai yra megalitai, statyti atskirose salose.
Vanuatu yra išlikę legendų apie priešistorinį karalių. Vienintelė istorinė karalystė (Tui Viti karalystė) Melanezijos regione įsikūrė Fidžyje XIX a. Bet jos įsikūrimas buvo nulemtas daugiau įtakos iš Polinezijos.
Atradimas ir tyrinėjimai
Melanezijos salas pirmieji „atrado“ Malajų salyno atstovai. Molukų salų Ternato imperija, nuo XV a. išplėtusi prekybinį tinklą, pasiekė vakarinę Naująją Gvinėją. Jie su vietos gyventojais užmezgė prekybinius santykius, o tik šioje saloje aptinkamų rojaus paukščių plunksnas padarė egzotine preke.
XIX a. Melaneziją politiškai dalinosi kolonijinės imperijos. Regiono dalybose dalyvavo keturios valstybės. Pirmieji įsitraukė Nyderlandai, tuo metu jau valdę Malajų salyną vakaruose. Jie prisijungė prie savo kolonijos Naujosios Gvinėjos vakarinę dalį. 1853 m. Napoleonui III bandant konkuruoti su britų kolonijomis Australijoje ir Naujojoje Zelandijoje, Prancūzija paskelbė savo kolonija Naująją Kaledoniją, kuri tapo Prancūzijos nuteistųjų pataisos vieta.
Konkuruodama su prancūzais 1883 m. Britų imperija nuo Australijos pakrančių prisijungė Naujosios Gvinėjos pietrytinę dalį, kur įkurta Papua kolonija (vėliau atiduota Australijai). Iš ten jie plėtė įtaką aplinkinėse salose, kolonizuodami Fidžį, Vanuatu (sutarė jį valdyti kartu su Prancūzija). Pačioje XIX a. pabaigoje į dalybas įsijungė ir Vokietija, kuri pareiškė teises į likusį neokupuotą Naujosios Gvinėjos šiaurės rytų trečdalį. Iš ten ji kolonizavo Bismarko salyną, o su Britų imperija pasidalino Saliamono salyną, sukurdama Vokietijos Naująją Gvinėją.
Prasidėjus I pasauliniam karui, Vokietijos kolonijos atiduotos administruoti Australijai. Ilgainiui ši sujungė Papua su buvusiomis Vokietijos kolonijomis, suformuodama junginį, dabar vadinamą Papua Naująja Gvinėja.
Po II pasaulinio karo per karą japonų užgrobtos kolonijos sugrįžo buvusiems kolonizatoriams: Australijai, Jungtinei Karalystei, Olandijai.
1945 m. buvusios Nyderlandų kolonijos Malajų salyne (Nyderlandų Rytų Indija) išsikovojo nepriklausomybę kaip Indonezija. Nepaisant to, Vakarų Naujoji Gvinėja liko Nyderlandų kolonija. Olandai ėmė ruošti vietos gyventojus savivaldai. 1959 m. išrinkta papuasų taryba ir 1961 m. pradėjo veikti Naujosios Gvinėjos Taryba (Nieuw Guinea Raad). Naujai valstybei buvo išrinktas pavadinimas Vakarų Papua, sukurta vėliava (Bintang Kejora).
Šių procesų metu Indonezija pagrasino karu, siekdama prisijungti naująją valstybę. 1962 m. Nyderlandai perdavė teritoriją laikinajai JT administracijai (UNTEA). Nepaisant to, 1963 m. Indonezija užgrobė valdžią buvusioje Olandijos kolonijoje. 1969 m. Indonezija buvo priversta suorganizuoti balsavimą dėl papuasų apsisprendimo (pepera). Dėl Indonezijos armijos grasinimų, balsavimas 100 procentų pripažino Indonezijos valdžią Vakarų Naujojoje Gvinėjoje.
Vėliau, dekolonizacijos metu (daugiausia XX a. VIII dešimtmetyje) dauguma buvusių kolonijų tapo nepriklausomos:
.png)