Schon 650 Jahre vor dem Zeitalter des Massentourismus erlebte Kuta seine erste große Fremdeninvasion. Wo sich heute sonnenhungrige Urlauber tummeln, betrat Gajah Mada mit seinem Heer die Insel, um sie nach erfolgreicher Eroberung dem Majapahit-Reich einzuverleiben. 1597 landete eine aus drei Schiffen bestehende holländische Handelsexpedition unter dem Kommando von Cornelius de Houtman vor Kuta. Sie hatten eine ziemlich erfolglose, von Mord und Meuterei geprägte Reise hinter sich, zur damaligen Zeit nicht ungewöhnlich. Bemerkenswert ist aber, dass dies der erste Kontakt Balis mit seinen späteren Kolonialherren gewesen sein muss.
Holländischen Chroniken zufolge entwickelte sich Kuta im 17. und 18. Jh. zum wichtigsten Hafen für Balis Sklavenhandel. Ein- bis zweitausend Balinesen wurden jährlich nach Java und zu anderen Inseln exportiert, ein Handel, an dem nicht zuletzt Balis Herrscher gut verdienten. Erst im 19. Jh. als die Rajas merkten, dass mit dem Verkauf von Naturprodukten an die Holländer noch mehr zu verdienen war, schlief der Sklavenhandel langsam ein.
Erste ausländische Handelsniederlassungen entstanden zu dieser Zeit an Kutas Küste. Sie wurden von den Balinesen geduldet, da diese Gegend für sie schon immer eine Art Niemandsland war: Ausgestoßene und Aussätzige zogen sich hierher zurück. Kutas Bevölkerung bestand in jenen Tagen aus einigen tausend Bauern und Fischern, Kaufleuten und Sklavenhändlern, Gesetzesbrechern, Verbannten und Aussteigern.
Der berühmteste und erfolgreichste unter den ausländischen Händlern Kutas war der Däne Mads Johansen Lange, der von 1839 bis 1856 hier lebte. Lange bezahlte er seine Einkäufe auf Bali mit chinesischen Kepeng-Münzen (mit einem Loch in der Mitte zum Auffädeln), der damals üblichen Währung. Der Däne scheint riesige Mengen dieser Münzen eingeführt zu haben, zweifellos zu einem für ihn äußerst profitablen Kurs. Der Reichtum ermöglichte Lange ein luxuriöses Leben. Sein palastähnliches Anwesen beherbergte ständig angesehene Gäste, auch balinesische Adlige, die mit Dinner-Partys unterhalten wurden. Mads Lange wurde während eines Besuchs bei einem einheimischen Prinzen vergiftet. Sein Palast stand ungefähr da, wo heutzutage der Nachtmarkt abgehalten wird. In der Nähe, auf einem Chinesen-Friedhof, findet man sein Grab und eine Gasse mit dem Namen Gang Tuan Lange.
Obwohl in den 30er-Jahren des 20. Jhs. schon etwa 100 Touristen pro Monat nach Bali kamen, schlief Kuta zu dieser Zeit wieder einen Dornröschenschlaf. Robert Koke, der 1936 das erste Hotel am Strand, das Kuta Beach Hotel, erbaute, sah „einen meilenlangen Sandstrand, gesäumt von Palmen, und keine Spur menschlicher Besiedlung, so weit das Auge reicht.“
Anfang der 40er-Jahre waren die Touristenziffern schon auf 250 pro Monat geklettert, aber mit der japanischen Invasion fand der Tourismus zunächst ein jähes Ende. Das erste Kuta Beach Hotel, schon damals im balinesischen Bungalow-Stil gehalten, wurde restlos zerstört. Das neue, 1955 errichtete Hotel gleichen Namens liegt einige 100 m vom alten Standort entfernt.
