Menurut cerita yang beredar di masyarakat Alor, kerajaan tertua di Kabupaten Alor adalah kerajaan Abui di pedalaman pegunungan Alor dan kerajaan Munaseli di ujung timur pulau Pantar. Suatu ketika, kedua kerajaan ini terlibat dalam sebuah Perang Magic. Mereka menggunakan kekuatan-kekuatan gaib untuk saling menghancurkan. Munaseli mengirim lebah ke Abui, sebaliknya Abui mengirim angin topan dan api ke Munaseli. Perang ini akhirnya dimenangkan oleh Munaseli. Konon, tengkorak raja Abui yang memimpin perang tersebut saat ini masih tersimpan dalam sebuah goa di Mataru.

Kerajaan berikutnya yang didirikan adalah kerajaan Pandai yang terletak dekat kerajaan Munaseli dan Kerajaan Bunga Bali yang berpusat di Alor Besar. Munaseli dan Pandai yang bertetangga, akhirnya juga terlibat dalam sebuah perang yang menyebabkan Munaseli meminta bantuan kepada raja kerajaan Majapahit, mengingat sebelumnya telah kalah perang melawan Abui.

Sekitar awal tahun 1300-an, satu detasmen tentara bantuan kerajaan Majapahit tiba di Munaseli tetapi yang mereka temukan hanyalah puing-puing kerajaan Munaseli, sedangkan penduduknya telah melarikan diri ke berbagai tempat di Alor dan sekitarnya. Para tentara Majapahit ini akhirnya banyak yang memutuskan untuk menetap di Munaseli, sehingga tidak heran jika saat ini banyak orang Munaseli yang bertampang Jawa.

Peristiwa pengiriman tentara Majapahit ke Munaseli inilah yang melatarbelakangi disebutnya Galiau (Pantar) dalam buku Negarakartagama karya Mpu Prapanca yang ditulisnya pada masa jaya kejayaan Majapahit (1367). Buku yang sama juga menyebut Galiau Watang Lema atau daerah-daerah pesisir pantai kepulauan. Galiau yang terdiri dari 5 kerajaan, yaitu Kui dan Bunga Bali di Alor serta Blagar, Pandai dan Baranua di Pantar. Aliansi 5 kerajaan di pesisir pantai ini diyakini memiliki hubungan dekat antara satu dengan lainnya, bahkan raja-raja mereka mengaku memiliki leluhur yang sama.

Pendiri ke 5 kerajaan daerah pantai tersebut adalah 5 putra Mau Wolang dari Majapahit dan mereka dibesarkan di Pandai. Yang tertua di antara mereka memerintah daerah tersebut. Mereka juga memiliki hubungan dagang, bahkan hubungan darah dengan aliansi serupa yang terbentang dari Solor sampai Lembata. Jalur perdagangan yang dibangun tidak hanya di antara mereka tetapi juga sampai ke Sulawesi, bahkan ada yang menyebutkan bahwa kepulauan kecil di Australia bagian utara adalah milik jalur perdagangan ini. Mungkin karena itulah beberapa waktu lalu sejumlah pemuda dari Alor Pantar melakukan pelayaran ke pulau Pasir di Australia bagian utara. Laporan pertama orang-orang asing tentang Alor bertanggal 8–25 Januari 1522 adalah Pigafetta, seorang penulis bersama awak armada Victoria sempat berlabuh di pantai Pureman, Kecamatan Alor Barat Daya. Ketika itu mereka dalam perjalanan pulang ke Eropa setelah berlayar keliling dunia dan setelah Magelhaen, pemimpin armada Victoria mati terbunuh di Philipina. Pigafetta juga menyebut Galiau dalam buku hariannya. Observasinya yang keliru adalah penduduk pulau Alor memiliki telinga lebar yang dapat dilipat untuk dijadikan bantal sewaktu tidur. Pigafetta jelas telah salah melihat payung tradisional orang Alor yang terbuat dari anyaman daun pandan. Payung ini dipakai untuk melindungi tubuh sewaktu hujan.