Kakawin Desawarnana (yang secara kurang tepat terkenal dengan nama Nagarakertagama) yang digubah Mpu Prapanca melaporkan bahwa ketika Hayam Wuruk berkeliling kerajaannya pada tahun 1359, ia mampir di Petukangan (dekat kota Panarukan sekarang). Di sana ia berkenan menerima para adipati dan mantri dari Madura, Blambangan, dan Bali yang datang menghadapnya untuk menyampaikan upeti. Adapun upeti yang dipersembahkan kepada maharaja itu adalah sapi, kerbau, kambing, babi, anjing, ayam, buah asam, dan kain tenun setempat. Sebagai balasan raja menganugerahkan kain patola, wastra halus buatan India yang mahal harganya.
Kehidupan keagamaan di Majapahit berjalan dengan toleransi tinggi sehingga sinkretisme agama Hindu dan Budha tumbuh subur. Tempat-tempat pemujaan, asrama pertapaan, dan percandian dibina dan dipelihara oleh kerajaan secara teratur. Di Madura candi-candi baru terus dibangun orang, seperti dekat Talang dan Jamburingin. Patung patung suci didatangkan dari Jawa karena tidak tersedia bahan batu yang sesuai di bumi Madura. Pengimporan patung suci itu mungkin pula dilakukan sebab seniman setempat dianggap tidak cukup baik mutu karyanya. Untuk memelihara makam pecandian dan tempat tempat pemujaan baru itu ditetapkan adanya desa sima yang dibebaskan dari beban pajak.
Bekas-bekas desa bebas pajak ini dapat disaksikan di dekat Sampang dan Sumenep, dan di pedukuhan kuno yang kadang kadang masih bernama Sema (seperti yang terdapat di pedalaman kecamatan Gapura).
Dalam Desawarnana diutarakan bahwa kedatangan tahun baru Saka selalu dirayakan secara meriah di kota Majapahit. Pusat-pusat pemerintahan di daerah seperti Madura mengirim perutusan ke ibu kota untuk mengambil bagian dalam pesta tahunan itu. Rombongan daerah itu terdiri atas para pemain untuk perlombaan adu ketangkasan dan kelompok seniman guna pementasan pertunjukan panggung, Bahkan Hayam Wuruk sendiri ikut berperan menari di atas panggung walaupun hanya di hadapan penonton terbatas.
Pertemuan tahunan yang melibatkan keikutsertaan bala tentara itu tentu diikuti pula oleh barisan prajurit dan pelaut Madura. Terkenallah nama dan peranan Mpu Nala sebagai panglima angkatan laut yang siap menggempur pengacau di seluruh penjuru kekuasaan Majapahit yang meluas dari ujung utara Sumatra sampai ke Irian. Rupanya ada keturunan Mpu Nala itu yang beberapa abad kemudian menjadi penguasa perang setempat di Tang Batang, Sekarang banyak keturunannya yang bermukim di Madura timur (anak-pinak Nalayudha, Naladipa, Natadiwangsa, dan Nalapraya).
Mahapatih Amangkubumi Gajah Mada dan Prabu Hayam Wuruk diberitakan selalu berupaya meningkatkan kesejahteraan rakyatnya. Untuk itu penataan tertib hukum dalam wilayah kerajaan benar benar mendapat perhatian penuh dari keduanya. Pengelolaan kerajaan besar itu dilakukan berdasarkan suatu sistem perundang undangan yang tersusun dalam sebuah keropak (buku yang terbuat dari lontar) yang disebut Kutara Manawa Darmasastra. Mungkin sekali perundang undangan itu merupakan pengembangan dan penyempurnaan bahan serupa yang berasal dari zaman raja Dharmawangsa.
Sesuai dengan perundang undangan yang diberlakukan itu, Madura serta wilayah Majapahit lainnya tidak memiliki rumah penjara. Sambil menunggu perkaranya diputuskan, seorang tertuduh atau terdakwa ditahan sementara di tempat berkumpul para tanda yang disebut patandban, istilah yang kelak dipakai di Madura sebagai padanan penjara. Jadi pidana kurungan tidak ada dan seseorang yang melanggar undang-undang mendapat bentuk hukuman lain sesuai dengan berat ringan kesalahannya.
Perusuh yang terbukti menculik, meracun dan menenung orang, membakar rumah penguasa, merusak kehormatan wanita atau membunuh orang tak bersalah akan dipidana mati. Orang yang menghina brahmana, mencuri sapi atau logam mulia, secara tak senonoh meraba wanita bersuami akan dihukum potong anggota tubuhnya. Denda dijatuhkan pada seseorang yang terpidana karena melukai orang, memakai kasta di atasnya, menghilangkan ternak titipan dan lain-lainnya. Selain itu dikenal pula bentuk hukuman pembayaran ganti kerugian, rebusan, serta penyitaan harta.
Menarik untuk dicatat bahwa pasal perundang undangan yang mengatur aturan atau perkelahian antara lain menyatakan bahwa “… jika ada orang sama bencinya, sama galaknya, sama beraninya, sama tajam keris atau tombaknya, saling bertengkar dan tikam-menikam sehingga salah seorang diantaranya terbunuh, yang masih hidup tidak dihukum oleh raja yang berkuasa, tidak dilakukan penuntutan ataupun didenda…” Rupanya pasal perundang-undangan demikian ini yang dulu memberikan landasan pembenaran bagi perkelahian carok yang khas Madura itu.
Perundang-undangan Kutara Manawa Dharmasastra ternyata tidak menindak orang yang berupaya menjaga harkat dirinya. Sebagaimana diketahui adat Madura menganggap carok sebagai tindakan mempertahankan kehormatan diri, yang seringkali ditimbulkan oleh adanya gangguan pada istri seseorang atau masalah wanita lainnya. Ternyata pula perundang undangan yang mengatur paradara (istri orang) pada waktu itu memang menjamin tidak akan adanya tuntutan pidana terhadap suami yang membunuh pria yang tertangkap basah mengganggu istrinya.
Dalam upaya meningkatkan kemakmuran kerajaan Majapahit, para pembesar Madura serta daerah kerajaan lain sering membuka hutan untuk dijadikan sawah dan tegalan. Dengan demikian di daerah yang subur suatu masyarakat agraria menjadi berkembang, Hasil utamanya adalah beras sehingga menjadi komoditas perdagangan yang penting untuk diekspor. Ini bertalian dengan kenyataan bahwa wilayah pesisir dan kota-kota pelabuhan Majapahit menjadi maju oleh semakin berkembangnya perdagangan internasional.
Pemberitaan Cina melaporkan ramainya pedagang India, Arab, Parsi, Sri Lanka, dan Cina memperjualbelikan batu permata, pecah belah porselen Cina, minyak wangi serta sutra. Beras, rempah-rempah dan hasil bumi lainnya merupakan komoditas perdagangan yang banyak dicari orang asing itu. Jadi Jawa merupakan transito dan tempat penumpukan bahan perdagangan dari nusantara bagian timur untuk diekspor ke luar negeri.
Sebaliknya Majapahit juga menjadi penghimpun barang-barang impor guna disebarluaskan ke seluruh wilayah kerajaan. Di samping mata uang setempat, uang tembaga Cina dari pelbagai masa banyak dipakai sebagai alat penukar yang sah dalam perdagangan antarbangsa itu.
Peran pelaut dan pedagang Madura dalam kegiatan yang sudah berlangsung sejak lama itu semakin maju pula. Jika pelautnya berfungsi sebagai penyedia sarana transportasi antar pulau, maka dengan melihat perkembangannya di zaman-zaman kemudian pedagang Madura waktu itu rupanya berfungsi sebagai saudagar keliling. Mereka hanya memperdagangkan barang sebanyak yang dapat dibawanya sendiri tetapi mungkin mahal harganya. Modal yang digunakannya berasal dari kaum hartawan, termasuk raja-raja dan bangsawan serta petugas pemerintahan yang berkuasa.
Dalam kancah perdagangan dan pergaulan antarbangsa yang ramai seperti itu dapatlah dimengerti jika lambat laun Bahasa Madura lalu memperkaya diri dengan menyerap kosakata dari Bahasa Hindi (cokka, konci, rote), Tamil (comette, jhudhu, kodbi), Cina (tokang, loteng, anglo), Parsi (salebbar, bajhân, pasar), dan juga Melayu (lesso, perro’, jhâu).
Dengan sendirinya para pedagang yang datang dari Timur Tengah dan berniaga di pelbagai kota pelabuhan Majapahit itu umumnya sudah beragama Islam. Karena seringnya terjadi hubungan sosial, lambat laun agama ini akan menyebar di kalangan sesama pedagangnya. Pedagang dan pelaut Madura diduga termasuk kelompok-kelompok awal yang ikut menjadi penganut Islam itu.
Kepercayaan yang baru masuk itu mungkin mendapat simpan mereka, terutama karena sifat kedemokrasiannya yang tidak membedakan lasta, keturunan, golongan, ataupun harta seseorang Lagipula keluasan cakupan ajarannya menyentuh seluruh gerak hidup manusia sehingga seakan-akan membenkan jawaban terhadap semua persoalan, yang menekankan keperluan mengeratkan persaudaraan dan kerukunan sesama umar beragama dalam menciptakan ketertiban bermasyarakat
