Bali telah dihuni oleh manusia sejak zaman Paleolitik, ini dibuktikan oleh penemuan alat kuno seperti kapak tangan di desa Sembiran dan desa Trunyan di Bali. Diikuti oleh periode Mesolitik, nenek moyang penduduk Bali saat ini mencapai pulau itu sekitar 3000 hingga 600 SebelumMasehi selama periode Neolitikum, ditandai dengan teknologi penanaman padi dan berbicara bahasa Austronesia. Periode Zaman Perunggu mengikuti, dari sekitar 600 SebelumMasehi hingga 800 Masehi.

Periode sejarah di Bali dimulai sekitar abad ke-8 Masehi, ditandai dengan ditemukannya prasasti nazar Buddhis tertulis yang terbuat dari tanah lempung. Tablet nazar Buddha, yang ditemukan di patung-patung stupa tanah liat kecil yang disebut stupika, adalah prasasti tertulis pertama yang diketahui di Bali dan berasal dari sekitar abad ke-8 Masehi. Stupika lainnya semacam itu telah ditemukan di Kabupaten Gianyar, di desa Pejeng, Tatiapi, dan Blahbatuh. Loka-lava berbentuk lonceng mirip dengan gaya stupa abad ke-8 seni Buddha Jawa Tengah yang ditemukan di Borobudur dan candi-candi Budha lainnya yang berasal dari periode itu, yang menunjukkan hubungan Sailendra dengan para peziarah Budha atau penduduk sejarah awal Bali. 

Pada awal abad ke-10, Sri Kesari Warmadewa menciptakan prasasti pilar Belanjong yang ditemukan di dekat jalur selatan pantai Sanur. Itu adalah tulisan tertua yang dibuat oleh penguasa yang ditemukan di Bali. Pilar tersebut bertanggal sesuai dengan kalender Saka India, pada 836 saka atau 914 Masehi. Menurut prasasti itu, Sri Kesari adalah seorang raja Buddha dari Dinasti Syailendra yang memimpin ekspedisi militer, untuk mendirikan pemerintahan Buddha Mahayana di Bali. Dua prasasti lain oleh Kesari dikenal di pedalaman Bali, yang menunjukkan konflik di pedalaman pegunungan di pulau itu. Sri Kesari dianggap sebagai pendiri dinasti Warmadewa, penguasa Bali yang diketahui paling awal, yang makmur selama beberapa generasi sebelum ekspansi dari pulau Jawa.

Tampaknya, pusat peradaban awal Bali pertama kali terletak di daerah Sanur di sebelah timur kota Denpasar, dan kemudian pusat politik, agama dan budaya pindah ke pedalaman utara, berkelompok di sekitar dataran selatan di masa kini di Kabupaten Gianyar; lebih tepatnya di pusat kerajaan tua di Bedulu, dekat Goa Gajah dan Gianyar. Kuil gua batu dan tempat pemandian Goa Gajah, dekat Ubud di Gianyar, dibuat sekitar periode yang sama. Ini menunjukkan kombinasi ikonografi Buddha dan Hindu Siwa. Beberapa ukiran stupa, stupika, dan gambar Boddhisattva menunjukkan bahwa dinasti Warmadewa adalah pelindung Buddhisme Mahayana. Namun demikian, agama Hindu juga dipraktikkan di Bali selama periode ini.