Ada cerita masyarakat bali yang menjelaskan bahwa Nusa Dua adalah ciptaan seorang ksatria sakti yang namanya Kebo Iwa.
Kesaktian Kebo Iwa pada saat itu menarik perhatian seorang raja dari keturuanan terakhir Dinasti Warma Dewa yang bernama Sri Astasura Bumi Banten.
Dan raja pun meminta Kebo Iwa untuk menjadi salah satu patihnya di wilayah Blahbatuh dan dikenal juga dengan gelar Raja Bedahulu.
Kata ‘Beda’ dalam kata “Bedahulu” jika diartikan adalah sebagai istilah kekuatan yang berbeda.
Cerita singkatnya, Kebo Iwa pun akhirnya menerima tawaran raja tersebut, dan Kebo Iwa pun diangkat menjadi Patih kerajaan.
Pada saat pengangkatan menjadi patih, Kebo iwa pun mengucapkan Janji setia di hadapan Raja Astasura Bumi Banten.
{bbseparator}
Dia menyatakan selama Kebo Iwa bernafas, maka janjinya Bali tidak akan pernah bisa ditaklukan kerajaan lain yang ingin menguasainya.
Tercatat dalam sejarah, pada zaman itu di Pulau Jawa terdapat sebuah kerajaan besar yang bernama Kerajaan Majapahit.
Majapahit pada saat itu dipimpin oleh seorang Raja bernama Tri Bhuwana Tungga Dewi, dan maha patih Gajah Mada.
Gajah Mada adalah maha patih kerajaan Majapahit yang sangat terkenal dengan Sumpah Palapanya
Yaitu sumpah untuk tidak menikmati kenikmatan dunia sebelum wilayah nusantara dipersatukan di bawah kekuasaan Majapahit.
Nah dengan bantuan dari patih Kebo Iwa yang sakti, Sri Astasura Bumi Banten menyatakan bahwa kerajaannya tidak mau tunduk.
{bbseparator}
Dia menolak kerajaannya tunduk patuh kepada Kerajaan Majapahit yang berkehendak untuk menaklukkan kerajaan di Bali.
Dan perang pun akhirnya tidak terelakan, namun dengan kedigjayaan Kebo Iwa , mereka bisa menahan serbuan pasukan Majapahit pada waktu itu.
Bahkan semua kapal-kapal perang Majapahit berhasil ditenggelamkan Kebo iwa dan pasukannya selagi berada di Selat Bali.
Sementara gagal menguasai kerajaan tersebut, akhirnya Maha Patih Gajah Mada pun mengatur sebuah siasat.
Salah satu siasatnya, Gajah Mada memberikan pujian kepada Baginda Sri Astasura Bumi Banten dan Patih Kebo Iwa.
Dan siasatnya yang lain membujuk Patih kebo Iwa untuk datang ke Majapahit untuk menikahi wanita pilihan raja majapahit yang berasal dari Lemah Tulis.
Mendapat pinangan tersebut, Kebo Iwa yang setia terhadap rajanya, meminta petunjuk dan restu dari baginda Sri Astasura Bumi Banten.
{bbseparator}
Dan sang raja pun tanpa mempunyai perasaan curiga merestui permohonan Patih Kebo Iwa tersebut.
Namun sebelum pergi ke Majapahit, sang Patih terlebih dahulu melakukan ritual Suci di Pura Uluwatu.
Tujuannya adalah untuk meminta restu serta kekuatan dari Sang Hyang Rudra.
Dan akhirnya Sang Hyang Rudra mengabulkan permintaan dan doa Patih Kebo Iwa.
Diberilah Kebo Iwa dua buah batu, yang dengannya kekuatan dan kesaktiannya menjadi lebih sakti lagi.
Selanjutnya Sejarah Pantai Nusa Dua Bali pun terus berlanjut,
{bbseparator}
Kebo Iwa akhirnya membawa salah satu dari batu pemberiaan tersebut ke desa Bedahulu dimana tempat mereka dilahirkan.
Sementara batu yang satunya lagi akan di bawanya pergi menuju ke kerajaan Majapahit.
Namun takdir bercerita lain, dalam perjalanannya ke tanah Jawa tiba tiba batu itu pecah menjadi dua dan jatuh di pinggir pantai.
Kemudian dipastulah batu tersebut untuk menjadi tempat kehidupan masyarakat.
Dan sejak dari itu, lama kelamaan batu tersebut seperti tumbuh membesar sehingga membentuk nusa yang dipanggil Nusa Dua.