Kerajaan Larantuka semula didirikan oleh seorang tokoh perempuan bernama Watowele bersama suaminya Pati Golo Arakian yang berasal dari keturunan bangsawan dari pulau Timor dari kerajaan Wehale merupakan tokoh peranakan perempuan bangsawan Jawa danjuga bangsawan kerajaan Wehale. erajaan itu semula lebih dikenal dengani kerajaan Ata Jawa sebelum akhirnya bernama Larantuka. Watowele senduru merupakan tokoh keramat yang diyakini dilahirkan dari gunung Ilemandiri dan merupakan cikal bakal keturunan satu – satunya dinasti yang memerintah kerajaan Larantuka dan juga dihormati sebagai keturunan langsung dari gunung / keturunan Ile Jadi. Baru pada pemerintahan keturunan ke – 3, yakni raja Sira Demon Pagu Molang kerajaan Larantuka menemukan bentuk pemerintahan tradisional yang lebih teratur yang tetap dipelihara hingga berakhirnya kerajaan Larantuka.

Cerita rakyat versi lain Watuwele dan Lenurat dikatakan sebagai penduduk asli Larantuka yang di sebut Ile jadi. Pada mulanya penghuni lereng Gunung Ile Mandiri dua orang kakak beradik yakni Lenurat dan adik perempuannya Watuwele. Kedua saudara tersebut seluruh tubuhnya berbulu, mencari makan dengan cara berburu binatang di hutan dengan menggunakan kukunya yang panjang sebagai senjata. Pada suatu ketika kedua saudara itu berpisah, Watuwele pergi kearah timur menetap di Woto dan Lenurat menetap di Likat Lamaboting Awo Lama Bunuk. Sementara itu di pesisir muncul pendatang baru yang dikenal sebagai orang paji. Lenurat kawin dengan gadis paji yang bernama Hadu Boleng Toniba Duli. Keturunan meraka menjadi nenek moyang penduduk Larantuka yang di sebut baipito. Sedangkan Watuwele menika dengan seorang tokoh bernama Pati Golo Arakiang. Riwayat pertemuan mereka di sebutkan : pada waktu Patigolo Arakiang mendarat di Krong di teluk Oka, ia kemudian berjalan melintas di hutan sampai di tempatnya Watuwele.

Ernst Vatter (1984) mengungkapkan Lenurat tidak di lahirkan dari seorang wanita seperti saudara perempuannya Watuwele. Ia timbul dari gunung. Ia muncul sebagai orang liar dan buas berambut dari kaki hingga kepala. Di rambutnya bersarang ular dan kadal. Kakak beradik ini tinggal di hutan di gunung Ile Mandiri. Pada waktu itu di gunung belum ada manusia yang tinggal. Manusia yang ada ialah orang paji yang tinggal di pantai dan daratan. Orang paji awalnya tidak mengetahui tentang Lenurat dan Watuwele.

Pada suatu malam ada seorang anak perempuan bernama Hadubole Teniba Duli yang melihat ada api di puncak gunung. Ia menyiruh saudaranya Pati Golo Arakiang pergi melihat ketempat tersebut. Ia melihat sebuah tunggku api yang telah kosong dan tumpukan abu dan arang. Untuk menghindari bahaya Pati Golo memanjat pohon. Tidak lama kemudian Watuwele kembali dari berburu. Ia mempinyai naluri yang tajam bahwa di tempatnya kedatangan orang asing yang belum menampakan diri.

Akhirnya di lihatnya Pati Golo Arakiang di atas pohon. Watuwele berjanji tidak akan menggangu Pati Golo Arakiang, oleh karena itu ia turun dari pohon. Mereka berdua menyalakan api dan membakar daging binatang buruan. Pati Golo Arakiang kebetulan membawa arak dan diminum berdua. Karena Watuwele minum terlalu banyak sehingga mabuk dan tertidur. Kesempatan itu digunakan oleh Pati Golo Arakiang untuk memotong kuku dan mencukur bulu badan Watuwele. Setelah di cukur barulah ketahuan bahwa Watuwele adalah seorang perempuan. Ia kemudian di beri pakian dan pada akhirnya mereka setuju untuk menjadi pasangan suami istri. Mereka mempunyai keturunan empat orang putra yang menjadi nenek moyang Raja Larantuka dan anggota Pou suku lema. Keturunan mereka di kenal sebagai orang demon atau demon nara. Sedangkan Lenurat yang kawin sama orang paji mempunyai anak lima orang dan menjadi nenek moyang penduduk Ile Mandiri dan nenek moyang orang paji atau Paji nara.

Ada versi cerita lain yang menyebutkan bahwa Raja Larantuka diturunkan oleh burung garuda dari gunang Ile Mandiri. Raja Larantuka ke-9 yang bernama Raja Ola dibaptis sebagai raja Katolik yang pertama dengan nama Don Constantino pada tahun 1645. Dilihat bahwa raja ke-9 yang di baptis pada tahun 1645 berarti dari raja pertama sebagai pendiri kerajaan sampai raja ke-9 terdapat 9 generasi. Dengan asumsi setiap generasi berjarak 25 tahun, maka dapat di perkirakan Kerajaan Larantuka berdiri pada tahun 1420. Pada masa tersebut, di wilayah indonesia bagian barat Kerajaan Majapahit masih berkuasa.

Pada masa lampau Larantuka atau Flores Timur merupakan salah satu wilayah pengaruh Kerajaan Majapahit yang di kenal dengan Jawa Muhan. Cerita bahwa Raja Larantuka di turunkan oleh burung garuda mengindikasikan adanya unsur pengaru Hindu mengingat burung garuda adalah burung mitologis dalam agama Hindu. Oleh karena itu dapat diduga bahwa raja pertama Larantuka diturunkan burung garuda adalah terkait dengan adanya unsur kekuasaan hindu yang meneguhkan raja pertama Larantuka.

Kerajaan Larantuka yang menguasai wilayah Demon membangun struktur kerajaan dengan istilah "Demon Lewo Pulo". Sepuluh wilayah atau lewo tersebut dipimpin oleh Kakang atau dikenal dengan Kakang Lewo Pulo. Kesepuluh wilayah Demon tersebut antara lain yaitu Pamakayo (Lewolein), Lewoingu (Lewolaga), Mudakaputu, Lewo Leba, Tana Boleng, Horowura, Lama Lera, Wolo, Lewo Tobi, Lewotala. Sedangkan orang Paji mendiami 5 daerah dipesisir pantai, oleh karena itu disebut "Paji Watan Lema" yang kemudian dikenal dengan sebutan "Solor Watan Lema". Padamulanya ada 6 kerajaan dilingkungan wilayah pengaruh Paji, antara lain yaitu Lohayong, Lamakera, Adonara, Terong, Lamahala, Serbiti (tetapi kerajaan serbiti hilang sehingga tinggal 5 buah kerajaan).