En 1510, le grand explorateur portugais Alphonso de Albuquerque découvrit l'île de Sumatra, initiant ainsi les voyages vers les « Iles des Epices ». Les navires s'en retournait vers l'Europe les cales pleines de poivre, de clous de girofles et de noix de muscade, et devaient faire face aux attaques de pirates, des Malais et des Javanais. En 1597, une flotte battant pavillon hollandais découvrit Bali, guidée par un ancien employé portugais, Cornelius Houtman. Lui et ses hommes tombèrent rapidement sous le charme de l'Ile Bénie des Dieux, et gagnèrent l'amitié du roi, un homme affable et bon qui possédait deux cents épouses, se déplaçait sur un char tiré par deux buffles blanc, et se distrayait du spectacle de cinquante nains dont les corps avaient été distordus pour ressembler à des poignées de kriss. Après un long séjour sur l'île, certains retournèrent en Hollande pour rapporter leur découverte du « nouveau Paradis », d'autres refusèrent de partir. La nouvelle fit sensation en Hollande, si bien qu'en 1601, le grand marchand Heemskerk fut envoyé à Bali chargé de riches présents pour le roi, qui en retour lui présenta une superbe Balinaise.

Les relations entre les Indes et l'Europe se détériorèrent rapidement après la création de la Compagnie Hollandaise des Indes Orientales, une organisation de marchands dont le but est l'exploitation sans limite des îles de l'archipel. Elle fomenta des guerres, initia le découpage et la vente des terres, établit le monopôle sur l'opium (un indigène pris entrain de commercer l'opium risquait la condamnation à mort), et collectait les taxes levées sur les habitants locaux, qui le plus souvent rapportaient bien plus que celles perçues sur les princes. La Compagnie tentait généralement d'acheter la faveur des Rajah afin de contrôler Bali, en leur offrant de riches présents. Si cela ne suffisait pas, elle usait d'intrigues politiques, vendant des armes aux ennemies des Balinais, voir en leur offrant assistance, en échange de futures concessions. La compagnie, malgré toutes ces manouvres, connue rapidement de graves difficultés, et passa finalement sous tutelle du gouvernement hollandais. Elle s'effondra finalement sans gloire en 1798.

A la même époque, la situation commença de se dégrader à Bali. Le Sultan de Surakarta, à Java, céda aux Hollandais ses « droits » sur Bali, en réalité inexistants. Mais les Hollandais tentèrent de les appliquer à la lettre. Les princes Balinais reconnurent la suprématie hollandaise, mais parvinrent à maintenir leur autonomie. En 1846, la question du droit coutumier balinais de confiscation des navires de commerces échoués sur les côtes de l'île entraîna la première expédition militaire contre le Nord de Bali. Après une série de batailles, les royaumes du Nord (Buleleng et Djimbrana) passèrent sous contrôle hollandais en 1882. Les princes Balinais furent amenés à signer un traité ratifiant l'interdiction des pratiques de piraterie et d'esclavage, et les engageant à ne permettre l'établissement d'aucune puissance européenne autre que la Hollande.