Pada jaman dahulu kala terdapat Kerajaan Medangkamulan yang terdapat di dataran Tengger. Saat itu Kerajaan sedang diperintah oleh Prabu Gilingwesi , raja ini dibantu oleh patih yang bijaksana dan cerdik yang bernama Patih Pranggulang. 

Meskipun Kerajaan Medangkamulan tentram dan makmur tapi Prabu Gilingwesi gusar karena putri nya, Putri Raden Ayu Tanjungsekar, enggan di persunting oleh lelaki manapun. Suatu malam Putri Raden Ayu Tanjungsekar bermimpi dalam tidur pulas nya, ia bermimpi sedang berjalan-jalan di taman yang indah, lalu ada suara pangeran yang sangat merdu memanggilnya, tapi aneh nya tiba-tiba muncul bulan purnama dilangit tanpa awan didalam mimpi nya, lalu bulan purnama itu perlahan masuk ke tubuh Putri Raden Ayu Sekartanjung, lalu tiba-tiba ia terbangun. Sebulan sesudah kejadiaan itu ada hal yang aneh terjadi , Putri Raden Ayu Sekartanjung ternyata hamil. Prabu Gilingwesi yang malu dan murka akibat putri nya yang hamil tiba-tiba tanpa suami itu pun lantas memerintahkan Patih Pranggulang untuk membawa Putri dan membunuh nya, akibat kesalahan itu.

Patih Pranggulang pun berangkat dengan Putri Raden Ayu Sekartanjung yang sedang hamil menuju hutan lebat, kurang lebih satu hari satu malam mereka berjalan lalu sampai lah mereka di hutan yang lebat. 

" Ki Patih Silahkan bunuh aku disini, tapi ingat, jikalau aku tidak mati terbunuh oleh mu, maka aku tidak bersalah sama sekali" ujar Putri Raden Ayu Sekartajung kepada Patih Pranggulang

Patih Pranggulang lalu mengayunkan pedang nya yang tajam kearah leher Putri Raden Ayu Sekartanjung tapi tiba-tiba pedang itu terpental, lalu ia mengulangi nya lagi namun tetap sama, semakin Patih Pranggulang berusaha kuat semakin jauh pula pedang nya terpental.

" Seperti nya benar yang  Tuan Putri katakan , Tuan Putri memang tidak bersalah, sebaik nya tuan putri meninggalkan tanah ini, hamba akan membuat kan rakit, berlayar lah melewati laut ini, pasti ada daratan lain disana, hamba sendiri tidak akan pulang kekerajaan dan akan bersemedi disini mendoaakan keselamatan Tuan Putri ", Ujar Patih Pranggulang kepada Putri Raden Ayu Sekartanjung.

Lalu berlayar Putri Raden Ayu Sekartanjung dengan rakit buatan Patih Pranggulang, saat malam tiba ketika bulan purnama tepat berada diatas, tiba-tiba perut Putri Raden Ayu Sekartajung terasa sakit, lalu lahir lah bayi laki-laki dari perutnya. Karena lahir diatas laut maka bayi itu dinamai Raden Sagara , sagara sendiri berarti laut dalam bahasa jawa.

Setelah beberapa hari diatas laut, tiba-tiba terlihat daratan, lalu mereka menepi disana, aneh nya saat menepi di daratan tersebut Raden Sagara yang belum lama lahir itu tiba-tiba meloncat ketanah dan lalu berjalan sembari badannya membesar. Lalu mereka berjalan terus sampai menemukan tanah yang luas yang lapang , disitu sangat sepi hanya ada mereka bedua disana ( dalam bahasa jawa tanah lapang sering disebut ara - ara) . Lalu disudut tanah itu ada sebuah pohon , dengan sarang lebah di atasnya, karena lapar mereka mencoba mengambil madu tersebut, ketika Raden Sagara hendak mengambil madu dari sarang lebah tersebut, lebah-lebah tersebut mempersilahkan mereka dengan terbang menjauh seperti sudah tau. Kemudian Putri Sekartanjung dan Anak nya Raden Sagara segera menikmati madu tersebut.

Karena mereka menemukan madu di tanah yang luas makan tanah tersebut diberinama Madura, yang berarati Madu yang berada di tanah lapang, berasal dari kata Madu dan ara-ara yang berarti tanah yang luas, dan kemudian kelak Raden Sagara akan menjadi raja dari tanah madura yang perama. (Dari berbagai sumber)