ჯერ კიდევ ჩვენს წელთაღრიცხვამდე 2000 წელს, ბალი დასახლებული იყო ავსტრონეზიური ხალხებით, რომლებიც აქ გადმოსახლდნენ კუნძულ ტაივანიდან სამხრეთ-აღმოსავლეთ აზიის სანაპიროს გამოვლით. კულტურულად და ენობრივად, ეს ხალხი ახლოს იყო ინდონეზიის არქიპელაგის სხვა ხალხებთან, ფილიპინებისა და ოკეანეთის ხალხებთან. კუნძულზე აღმოჩენილია ამ პერიოდის ქვის იარაღები.

ჩვ. წ. I საუკუნისთვის, ბალის კულტურა განიცდიდა, ინდურ, ჩინურ და განსაკუთრებით ჰინდუს კულტურის გავლენას. კუნძულის ადგილობრივი სახელი ყოფილა Bali dwipa (კუნძული ბალი), რაც აღმოჩენილია მრავალ წარწერაში.

1293–1520 წლებში, ბალი შედიოდა მაჯაპახიტის იმპერიის შემადგენლობაში. XV საუკუნეში, იმპერიის დასუსტებისას, მასიური სახე მიიღო ინტელექტუალთა გადასახლებამ კუნძულ იავიდან ბალიზე.

კუნძულის პირველი კონტაქტები ევროპელაბთან, შედგა 1585 წელს, როდესაც ბალის პორტუგალიელები მოადგნენ. 1597 წელს, კუნძულს ეწვია ნიდერლანდელი მკვლევარი კორნელის დე უტმანი, რომელმაც 1602 აქ დააარსა ჰოლანდიის ოსტინდოეთის კომპანია. ამან საფუძველი ჩაუყარა ორ-ნახევარი საუკუნის შემდეგ ნიდერლანდების კოლონიურ კონტროლს მთელს ინდონეზიის არქიპელაგზე. ნიდერლანდური კოლონიზაცია კონკრეტულად ბალიზე იწყება 1840 წელს.