Dalam catatan sejarah, perpindahan bangsa-bangsa secara besar-besaran dari Asia tenggara terjadi dalam kurun waktu yang sangat panjang (antara 4000-2000 sebelum Masehi). Kejadian ini antara lain berasal dari daratan asia dimana semakin bertambah pesatnya kerajaan-kerajaan Cina. Karena kepesatan perkembangan kebudayaannya mereka lalu meluaskan pengaruh kekuasaannya ke arah selatan. 

Kawasan yang langsung terkena dampaknya adalah wilayah Tibet (yang merupakan tanah leluhur bangsa Burma) dan daerah Yunan (yang semula dihuni orang Thai dan Vietnam). Akibat dari mengalirnya kedatangan bangsa Cina tersebut, maka bangsa-bangsa Burma, Thai dan Vietnam terpaksa menyingkir lebih ke selatan.

Hingga pada akhirnya, perpindahan mereka lalu melahirkan cikal bakal bangsa-bangsa Proto Melayu yang mana pada waktu itu bermukim di wilayah Burma, Siam dan Indochina. Fenomena itu menyebabkan kelompok bangsa-bangsa tersebut menjadi tercerai-berai. Hingga sebagian dari mereka melakukan perpindahan ke daerah pantai. Namun tidak sedikit diantara mereka yang terus ke selatan, mengarungi laut ataupun melewati Semenanjung kemudian menyeberangi selat hingga mencapai pulau-pulau di Nusantara.

Perahu Yunan ketika mengarungi lautan

Proses perpindahan melintasi lautan tersebut tidak berlangsung sekaligus. Kebanyakan dari mereka berangkat secara bergelombang kelompok demi kelompok dalam kurun waktu kurang lebih 2000 tahun. Karena tidak bersamaan meninggalkan tanah asalnya itu maka kelompok-kelompok tersebut tiba di tempat yang berlainan pulau di Nusantara. Walau pada mulanya mereka serumpun bangsa dan bahasanya, lama-kelamaan pemisahan Geografis menyebabkan terjadinya perbedaan yang makin membesar. 

Salah satu kelompok bangsa yang pindah mengarungi laut itu terdampar ke suatu pulau kecil yang terletak di utara, ujung timur pulau Jawa. Para pendatang ini lalu menetap di sana untuk kemudian menjadi nenek moyang bangsa Madura. Seperti bangsa Piah, Campa dan Jai di Kocincina mereka mengacu pada apai dengan mana apoy, menyebut istrinya "bine" dan memakai kata "ella" untuk menyatakan jangan. 

Bangsa Yunan

Berbeda dengan bangsa-bangsa lainnya. Bahasa mereka mengenal konsonan rangkap seperti bassa, cacca, daddi, kerrong dan pennai. Kalau dibandingkan dengan bangsa-bangsa yang mendiami pulau-pulau di sekitarnya, leluhur orang Madura ini umumnya memiliki tengkorak yang celah matanya lebar mendatar dengan tulang pipi lebih menonjol. Raut muka mereka tidak begitu halus dan warna kulitnya lebih gelap.

Dari beberapa hasil penelitian sejarah belum dapat dipastikan apakah sesampainya di pulau yang akan menjadi tempat huniannya cikal-bakal suku bangsa Madura itu menjumpai penduduk asli Nusantara. Jika ada maka penduduk asli itu akan dapat dikalahkan sebab mereka masih berkebudayaan batu tua (paeolitik). Adapun pendatang baru dari utara itu telah berkebudayaan batu baru (neolitik), seperti ditunjukkan oleh peninggalan mereka yang diketemukan di Madura. Jadi mereka telah berkemampuan mengupam atau mengasah batu menjadi beliung atau kapak persegi, yang dapat pula dijadikan pacul.

Setelah ratusan tahun di Madura maka para pendatang baru itu menjadi beranak-pinak dan terpencar-pencar ke seluruh pulau. Bahkan pulau-pulau kecil di sekitar Madura dihuninya juga, seperti pulau Sepudi dan Kangean di timur, pulau Mandangin di selat Madura dan pulau Masalembu serta Bawean di laut Jawa. Mereka bermukim dalam kelompok-kelompok yang besarnya di tentukan oleh kesuburan tanah atau daya dukung ekologi setempat. 

Beberapa kelompok ini jumlahnya sampai ratusan orang sehingga kemudian membentuk satuan-satuan tersendiri namun masih terikat satu sama lain oleh kesamaan bahasa. Dan lama-kelamaan memunculkan dialek setempat yang terhadap perbedaannya dari barat (Bangkalan), tengah (Sampang dan Pamekasan), timur (Sumenep) dan timur sekali (Kangean). Lambat laun timbul pula ras keterkaitan pada tanah kelahiran dan pada kelompok masyarakat yang menghuni nya karena kebersamaan peruntungan dan kebersamaannya. 

Jarak Geografis pusat-pusat pemukiman yang berjauhan itu menyebabkan perbedaan di antara mereka itu semakin mantap. Apalagi karena perkembangan selanjutnya mengikuti alur sejarah yang agak berlainan untuk setiap wilayah.

Bejana

Peninggalan purbakala berupa kapak dan bejana perunggu (sebagai pengejawantahan peradaban Dongson) yang se-type dengan yang ada di daratan Cina Selatan dan Asia Tenggara juga diketemukan di wilayah Sampang, ini memberi bahwa tidak terputusnya hubungan Madura dengan daratan Asia, yang mungkin dilakukan untuk keperluan perdagangan. Tetapi karena Madura tidak menghasilkan komoditas perdagangan yang berarti untuk dipertukarkan, maka timbul dugaan bahwa mereka ini merupakan pedagang perantara. Mungkin juga hanya bermodalkan pengetahuan tentang seni berlayar, maka pelaut-pelaut Madura menyediakan perahunya untuk membawa pedagang dari bangsa lain mengarungi lautan lepas.

Kerajaan-kerajaan kecil di Madura tentu menjadi merdeka sebentar sampai raja Airlangga berhasil meng-konsolidasi kekuasaannya pada tahun 1017. Keutuhan Negara cepat pulih dan kesejahteraan rakyat segera dikelola kembali. Kegiatan perdagangan luar Negeri dengan Cina dan Negara Asia lainnya ramai lagi. Di kerajaan Airlangga pedagang asing membeli gading, cula badak, mutiara, kapur barus, gaharu, cendana, rempah-rempah serta kulit penyu dan burung. Beras merupakan komoditas hasil bumi Jawa yang penting untuk bekal berlayar yang memakan waktu berbulan-bulan. Saudagar asing membayar pembeliannya dengan uang emas dan perak. Di samping itu mereka memasukkan sutra dan pecah belah dari proselen.

Dari pemberitaan Cina kita mengetahui bahwa kerajaan Airlangga itu bernama Pu Chia Lung (Panjalu). Pelabuhan utamanya adalah Chung Kia Lu (Ujung Galuh) yang terletak dekat muara sungai Brantas. Di sebelah timurnya lagi terdapat pelabuhan Ta pan (Sampang/Ketapang) yang merupakan sebuah kota penting kerajaan bawahan. Dari sini jelas bahwa peran Madura sebagai penjaga jalur lalu lintas maritime kerajaan Panjalu itu sangatlah besar.

Dengan adanya perahu bercadik (yang sekarang masih ada serta pengembangannya dalam bentuk jukong) dimungkinkan ada di antara rombongan pendatang tersebut yang sampai ke pulau kecil ini dengan rakit. Dugaan ini didasarkan pada salah satu mythology yang menggambarkan cara orang-orang tua Madura tempo doeleo menjelaskan asal usul leluhurnya. Mereka menganggap dirinya keturunan sang Segara, pangeran laut yang sampai ke pulau ini dalam kandungan ibunya yang terdampar di pantai utara. Madura dengan menaiki rakit.

Kebanyakan rumah-rumah adat masyarakat Madura dibuat menghadap ke selatan, hal ini disebabkan oleh sejarah perjalanan leluhur mereka yang datang dari arah utara ke selatan dikarenakan terdesaknya nenek moyang mereka dari daerah asalnya, dan route perjalanan yang dilakukan untuk menyelamatkan diri ditempuh melalui jalur laut menuju daerah selatan. Sejak peristiwa itu bagi bangsa ini laut merupakan symbol dan keselamatan dan masa depan yang penuh harapan, akan tetapi ada pula pendapat yang menyatakan bahwa, masyarakat Madura yang dikenal sebagai pelaut-pelaut tangguh menganggap laut sebagai cerminan hidup yang penuh dengan tantangan dan gelora yang harus dihadapi dalam mengarungi kehidupannya serta harapan masa depannya.

Laut juga menjadi cermin pelambang kebebasan jiwa petualangannya dan wadah ekspresi rasa kemerdekaannya. Dalam perjalanan sejarah kehidupan leluhur bangsanya mereka pernah mendapat ancaman bahaya yang datang dari pedalaman di utara. Karena itu mudah lah di mengerti jika mereka selalu menggapai ke arah selatan yang waktu itu berupa laut. Orientasi ke laut secara luas dapat dimaknakan ka lao’ dalam bahasa Madura (yang berarti ke selatan, yaitu penunjuk arah lawan utara). Berbeda dengan orang Jawa, mythology Nyai Loro Kidul yang mengagung-agungkan pantai laut selatan Samudera India tidak mempunyai akar dalam tradisi asli mythology rakyat Madura.

Hanya sayang tentang keberadaan pemerintahan di Madura sejak masa Airlangga, hanya berita dari China dan tak ada sumber lain yang menungjangnya, sehingga kurang kuat untuk dijadikan acuan. Dan tidak ada sisa situs peninggalan sejarah sebagai bukti kebenarannya. Dengan demikian maka Arya Wiraraja lah ditentukan sebagai Adipati pertama di Sumenep / Madura, itu berdasarkan beberapa sumber yang cukup kuat, diantaranya adalah Prasasti Mula Malurung, Kitab Nagarakretagama, Serat Pararaton, Kidung Harsawijaya, Kidung Wijayakrama, Kidung Ranggalawe dan lain sebagainya. 

Menurut tulisan Drs Abdurrahman (manta Bupati Sumenep), bahwa di Sumenep/Madura sebelum Arya Wiraraja sudah ada pemerintahan yang berpangkat "Akuwu". Tapi sangat disayangkan tidak ada tulisan yang jelas tentang hal tersebut. Dan sangat disayangkan prasasti Mula Malurung lempengan VI A dan B 12 hilang, sehingga penjelasan tentang pemerintahan sebelum Arya Wiraraja kurang jelas.