Na ostrov Bali dorazili první obyvatelé, australo-asiaté – původem z Taiwanu, už kolem roku 2000 před n. l., ze kterého také pocházejí nejstarší dochovalé nálezy kamenných nástrojů, lodí a koster.
Během 4. – 8. století se po ostrově šíří hinduismus a buhismus, které byli dále rozvíjeny jávským králem.
Od dvanáctého století začíná mít vliv na Bali sousední ostrov Jáva. Ve čtrnáctém století si Bali podmaní jávský vládce Mandžapahit, což způsobí výrazné společenské i kulturní změny, mimo jiné zavede na Bali kastovní systém. Ne všichni obyvatelé Bali se chtěli přizpůsobit, proto se celé skupiny odebírají do odlehlých pralesů a hor, aby zde založily nové vesnice a ubránily se změnám. Dodnes žijí zcela odlišným způsobem, který zachovává tradiční zákony, na rozdíl od pobřežních oblastí.
Po pádu Madžapahita se začíná na Jávě vzmáhat islám, který doslova zaplavuje celý ostrov. Vzhledem k tehdejší síle islámu je dnes s podivem, že ostrov Bali zůstal výrazně hinduistický a buddhistický. Před islámem na Bali u prchla také královská rodina.
Koncem 16. století se na Bali začínají vyloďovat nizozemské expedice a velice rychle se zabydlují, i když s nápadem kolonizace přicházejí až o dvě století později. Na ostrov přináší křesťanství a otevírají trh s rýží, opiem, otroky a ženami. Trh kvete a ostrovu si poprvé všímá i Británie.
V roce 1816 Británie ovládne okolní ostrovy a vzpouzející se Bali přitáhne pod vlastní křídla ozbrojenými silami. O dva roky později však ostrov navrátí Nizozemsku, které uplatňuje čím dál větší sílu na podmanění tradic a zákonů.
V průběhu druhé světové války okupuje celou Indonésii Japonsko.
Po skončení války v roce 1945 se Nizozemsko pokusilo získat zpět své kolonie, ale zmatku využil první indonéský prezident Sukarno, který hbitě vyhlásil nezávislost. V roce 1949 byla Indonésie uznána samostatnou zemí.
V roce 1963 vybuchla sopka Gunung Agung a její mohutná erupce zabila tisíce lidí a zničila velkou část ostrova.
V sedmdesátých letech se začíná rozvíjet turistika, která formuje Bali do podoby, jak jej známe dnes.