Cafwyd hyd i weddillion Homo erectus yn dyddio i tua 600,000 o flynyddoedd yn ôl at ynys Jafa. Yn y cyfnod yma, roedd lefel y môr yn is nag yw yn awr, ac roedd rhai o'r ynysoedd wedi eu huno a'i gilydd ac a'r tir mawr.

Yn y cyfnod rhwng y 7g a'r 14g, sefydlwyd nifer o deyrnasoedd ac ymerodraethau ar ynysoedd Sumatra a Jafa, oedd yn y cyfnod yma dan ddylandwad Hindwaeth a Bwdhaeth. Y pwysicaf o'r rhain oedd Srivijaya, Majapahit a Mataram. Yn y cyfnod yma yr adeiladwyd remlau mawr Borobudur a Prambanan. Daethpwyd a chrefydd Islam i'r ynysoedd tua 1300 gan farsiandïwyr Arabaidd, a daeth yn brif grefydd y mwyafrif o'r ynysoedd.

Morwyr o Portiwgal oedd yr Ewropeaid cyntaf i gyrraedd ynysoedd Indonesia yn 1512. Dilynwyd hwy gan fasnachwyr o'r Iseldiroedd a Phrydain. Yn 1602 sefydlwyd Cwmni India'r Dwyrain yr Iseldiroedd (VOC), a'r cwmni yma oedd y pwer mawr yn yr ynysoedd hyd 1800, pan ddaethant yn rhan o ymerodraeth yr Iseldiroedd dan y llywodraeth.

Yn ystod yr Ail Ryfel Byd meddiannwyd yr ynysoedd gan Japan. Ar ddiwedd y rhyfel yn Awst 1945, cyhoeddodd y cenedlaetholwyr Indonesaidd, dan arweiniad Sukarno, wladwriaeth annibynnol. Ceisiodd yr Iseldiroedd ad-ennill grym, ond wedi cryn dipyn o ymladd gorfodwyd hwy i gydnabod annibyniaeth Indonesia yn Rhagfyr 1949.

Sukarno, Arlywydd cyntaf Indonesia

Bu Sukarno yn arlywydd hyd 1968. Gwanychwyd ei safle yn ddirfawr gan ddigwyddiadau 30 Medi 1965, pan laddwyd chwech cadfridog yn yr hyn a hawlid oedd yn ymgais gan Blaid Gomiwnyddol Indonesia (PKI) i gipio grym. Ymatebodd y fyddin, dan arweiniad y cadfridog Suharto, trwy ladd miloedd lawer o gomiwnyddion ac eraill y dywedid eu bod mewn cydymdeimlad â hwy. Credir i rhwng 500,000 a miliwn o bobl gael eu lladd. Daeth Suharto yn arlywydd yn ffurfiol ym mis Mawrth 1968.

Yn ystod cyfnod Suharto bu tŵf economaidd sylweddol, ond effeithiwyd ar yr economi yn ddifrifol gan broblemau economaidd Asia yn 1997 a 1998. Cynyddodd protestiadau yn erbyn Suharto, ac fe'i gorfodwyd i ymddiswyddo ar 21 Mai 1998. Yn 1999 pleidleisiodd Dwyrain Timor i adael Indonesia a dod yn wladwriaeth annibynnol.

Yn dilyn ymddiswyddiad Suharto, sefydlwyd trefn fwy democrataidd, a chynhaliwyd yr etholiad uniongyrchol cyntaf i ddewis Arlywydd yn 2004. Yr Arlwydd presennol yw Susilo Bambang Yudhoyono.