Rombongan dari bangsawan Demak yang berjumlah puluhan Kepala Keluarga ini pimpin oleh Pangeran Sedo Ing Lautan dan menetap di Palembang Lama (1 ilir), yang saat itu Palembang sudah dibawah pimpinan Dipati Karang Widara, keturunan Demang Lebar Daun.
Dari catatan naskah kuno yang sudah dialih-bahasakan oleh Wildan Aulia dengan judul Suntingan Teks Asal Usul Raja-raja Palembang (halm. 195), yang diterbitkan oleh Perpusnas Press Jakarta tahun 2020, tercatat asal mula kedatangan mereka sbb :
"Pangeran Surabaya, dan Pangeran Mandi Pendawan beranakan Panembahan Juro (Jano) yang wafat di laut, dan Pangeran Seriai beranakkan Pangeran Siding lautan beranakkan Kiai Hang Sura beranakkan Kiai gedeng sura dan Kiai Gedeng Ilir, maka baginda dua bersaudara itulah yang berpindah ke negeri Palembang dengan segala rakyatnya, dan waktu sudah wafat kiai gegeng sura, maka diganti oleh Kiai Gedeng Ilir berjuluk pula kiai gedeng sura muda menjadi raja negeri Palembang, maka Baginda itu beranak delapan orang yang tua perempuan bernama (N)yai Geding Pembanjun, bersuami Temenggung Mancanegara, misam (misan)… sendiri, dan kedua Ratu… yang di negeri J… yang ketiga Ki Emas… Depati yang ko… Pangeran Madi… Sogoh, dan yang kelima Pangeran Medialit, yang keenam Pangeran Siding Puro, dan yang ketujuh Ni Emas Kembar…, yang kedelapan Ni Emas Kembar juga namanya sebab ia… kembar.”
Dengan berjalannya waktu, Pangeran Sedo Ing Lautan sebagai pemimpin pelarian dan atas kesepakatan bersama dengan penguasa lainnya di Palembang yang saat itu masih memimpin kerajaan-kerajaan kecil setelah ditinggal oleh Bajak Laut Cina, membentuk sistem pemerintahan secara formal untuk mengawasi dan mengelola perdagangan lada dan perdagangan lainnya di Palembang. Untuk itu disepakati dan didirikanlah Kerajaan Palembang yang bercorak Islam dan selanjutnya membuat Pemukiman baru dan Keraton Kuto Gawang sebagai pusat pemerintahan serta Masjid Agung sebagai pusat pembinaan agama di masyarakat.
Dalam kesepakatan itu diangkatlah Ki Gede Ing Suro Tuo, anak dari Pangeran Sido Ing Lautan, sebagai pemimpin dan Raja Kerajaan Palembang pertama dan tercatat berkuasa selama 22 tahun (1552 - 1573). Selanjutnya oleh karena beliau tidak berputera, maka ia mengangkat keponakannya menjadi penggantinya dengan bergelar pula Ki Gede Ing Suro Mudo (1573 - 1590). Setelah wafatnya ia di ganti oleh Kemas Adipati selama 12 tahun. Kemudian digantikan oleh anaknya Den Arya lamanya 1 tahun.
Pangeran pengganti selanjutnya adalah Pangeran Ratu Madi Ing Angsoko Jamaluddin Mangkurat I (1596 - 1629). Disaat kepemimpinan beliaulah terjadi penyerangan yang dilakukan oleh kesultanan Banten yang dipimpin langsung oleh Sultan Banten, Sultan Maulana Muhammad, pada tahun 1596 yang berakibat kekalahan di pihak Kesultanan Banten dan dibarengi dengan meninggalnya Sultan Banten tersebut.
Pengganti selanjutnya ialah adiknya, yaitu Pangeran Madi Alit Jamaluddin Mangkurat II (1629 - 1630). Setelah wafat diteruskan pula oleh adiknya yang bernama Pangeran Sedo Ing Puro Jamaluddin Mangkurat III (1630 - 1639), wafat di Indra laya. Lalu digantikan oleh kemenakannya yang bernama Pangeran Sedo Ing Kenayan Jamaluddin Mangkurat IV (1639 - 1650) bersama dengan isterinya Ratu Sinuhun. Ratu Senuhun inilah yang dikenal sebagai penyusun "Undang-undang Simbur Cahaya" yang mengatur adat pergaulan bujang gadis, adat perkawinan, piagam dan lain sebagainya di Kerajaan Palembang. 
Sebagai ganti Pangeran Sido Ing Kenayan ialah Pangeran Sedo Ing Pesarean Jamaluddin Mangkurat V (1651 - 1652) bin Tumenggung Manca Negara. Tongkat estafet selanjutnya dipegang oleh puteranya yang bernama pangeran Sedo Ing Rejek Jamaluddin Mangkurat VI (1652 - 1659) sebagai raja Palembang. Beliau raja yang alim dan wara'.
Pangeran Sido Ing Rajek inilah yang merupakan Pemimpin terakhir dari Kerajaan Palembang yang di tahun 1659 M diserang oleh oleh Vereenigde Oostindische Compagnie (VOC) dipimpin oleh Laksamana Joan Van der Laen yang berakibat terbakarnya Keraton Kuto Gawang sampai habis.
Keraton Kuto Gawang, sebagaimana yang sekarang dapat divisualisasikan dari catatan dan lukisan Joan Nieuhaf dalam buku nya “Voyages and Travels to East Indies tahun 1653 – 1670 “ terlihat layaknya sebuah Ibukota Kerajaan Palembang yang dihuni oleh rakyat Palembang saat itu. Keraton ini berbentuk empat persegi panjang yang dibentengi dan dikelilingi oleh dinding dinding kayu tebal dari kayu Unglen dan Kayu Besi serta juga dihilirnya dilindungi oleh Benteng Pertahanan Manguntama di Pulau Kemaro serta Benteng Tambak Bayo dan Benteng Martopuro di Plaju dan Sungai Gerong, sebagaimana tergambar jelas di lukisan La Ville de Palimbang dans I'lle de Sumatera dibawah ini.
