Kota Palembang hingga kini masih dipercayai masyarakat Melayu sebagai tanah leluhurnya. Menurut kisah, di kota inilah hadir seorang tokoh yang menjadi cikal bakal Raja Melayu pertama yaitu Parameswara yang turun dari Bukit Siguntang. Pada saat yang bersamaan, Kerajaan Sriwijaya runtuh, maka bermunculan kekuatan-kekuatan lokal seperti Panglima Bagus Kuning di hilir Sungai Musi, Si Gentar Alam di daerah Perbukitan, Tuan Bosai dan Junjungan Kuat di daerah hulu Sungai Komering, Panglima Gumay di sepanjang Bukit Barisan. Kemudian Parameswara meninggalkan Palembang bersama Sang Nila Utama menuju Tumasik. Tanah Tumasik diberi nama Singapura oleh Parameswara.

Pada saat pasukan Majapahit akan menyerang Singapura, Parameswara bersama pengikutnya pindah ke Malaka, kemudian mendirikan Kerajaan Malaka. Beberapa keturunannya membuka negeri baru di daerah Pattani dan Narathiwat (sekarang wilayah Thailand bagian selatan). Hubungan dagang yang kuat dengan orang–orang Gujarat dan Persia menyebabkan perekonomian Malaka berkembang pesat. Kemudian Parameswara memeluk agama Islam dan mengganti namanya menjadi Sultan Iskandar Syah. 

Kota Palembang menjadi kota tak bertuan, tidak ada penguasa tunggal atas kota dagang ini. Namun kegiatan perekonomian tetap berjalan. Perdagangan antarbangsa berjalan dengan baik. Di kota ini pula bermukim para pembesar dan priyayi pendukung utama Kesultanan Demak, penguasa baru tanah Jawa. Mereka menyingkir dari Demak setelah kalah perang melawan Kerajaan Pajang pada tahun 1528. Rombongan asal Demak ini dipimpin oleh Kiai Gedeng Suro atau Ki Gede Ing Suro.

Selain pembesar dan priyayi, turut serta pula pasukan yang dipimpin oleh Raden Patah. Mereka memilih Palembang sebagai tempat yang aman. Selain karena Raden Patah (bergelar Jimbun Abdurrahman Panembahan Palembang Sayyidina Panatagama) adalah bangsawan Demak kelahiran Palembang. Beliau tumbuh sejak kecil di kota ini bersama ibunya, Putri Campa.

Raden Patah, Ario Damar dan Pati Unus, adalah tokoh dibalik hancurnya Kerajaan Majapahit. Mereka dikenal dari Ekspedisi Pamalayu. Raden Patah berhasil membangun kembali Palembang setelah Kerajaan Sriwijaya secara perlahan mulai melemah. Berselang kemudian, Majapahit mulai dilanda kekacauan, pemberontakan dan pecahnya perang saudara.

Ario Damar sendiri pada saat itu adalah seorang Mangkubumi Kerajaan Sriwijaya. Beliau memeluk Islam sejak kedatangan Raden Rahmat. Menjadi seorang muslim, Ario Damar mengganti namanya menjadi Ario Abdullah, yang populer dengan sebutan Ario Dillah.

Kehadiran Ki Gede Ing Suro di kota Palembang, memicu kedatangan pemukim-pemukim muslim baru dari Demak, Pajang dan Mataram. Mereka datang ke Palembang demi menghindari konflik politik berkepanjangan di tanah Jawa.

Sebuah kerajaan Islam di Palembang akhirnya resmi berdiri pada tahun 1552 secara politik dari Kesultanan Demak. Adalah Ki Mas Hindi, disebut pula Pangeran Ratu atau Pangeran Ario Kusuma Abdurrohim, yang memiliki nama lain, Susuhunan Abdurrahman Khalifatul Mukminin Sayyidul Imam, sebagai Sultan pertama kerajaan Islam di tanah Palembang. Beliau bergelar Sultan Jamaluddin Candi Walang, atau Sultan Ratu Abdul Rahman. Kerajaan Islam ini diberi nama Kesultanan Palembang Darussalam.

Sultan Jamaluddin kemudian diganti oleh Sultan Mansyur. Beliau didampingi seorang ulama besar, Tuan Faqih Jalaluddin. Setelah Sultan Mansyur, Kesultanan Palembang dipimpin oleh Sultan Mahmud Badaruddin, yang dikenal pula sebagai Sultan Lemah Abang.

Kesultanan Palembang Palembang Darussalam menggabungkan kebudayaan maritim peninggalan Sriwijaya dan budaya agraris Majapahit. Palembang kemudian berkembang menjadi pusat perdagangan yang paling besar di Semenanjung Malaka. Hadirnya Kesultanan Palembang Darussalam ini menjadi lembaran baru bagi kota Palembang sejak keruntuhan Sriwijaya. Hukum Islam diterapkan dalam aturan tatanegara dan ekonomi.

Ki Gede Ing Suro merupakan tokoh utama dibalik berdirinya Kesultanan Palembang Darussalam. Setelah wafat pada tahun 1587, beliau dimakamkan di sebuah daerah yang kini berada di Kelurahan I Ilir, kota Palembang. Setelah beliau dimakamkan, berturut-turut dimakamkan para pembesar Demak lainnya dan keluarganya, hingga mencapai 38 makam. Kompleks pemakaman ini kemudian dikenal sebagai Taman Purbakala Ki Gede Ing Suro.

Kompleks makam berupa bangunan fondasi yang terdiri dari tiga bangunan utama. Bangunan pertama memiliki luas 54 meter persegi, dengan tinggi 1,2 meter. Bangunan ini berdiri diatas dua lapik, lapik pertama berukuran 7 meter x 3,7 meter. Lapik kedua berukuran 16 meter x 11 meter. Diatasnya berdiri batur dengan tangga masuk yang berada di sisi selatan. Pada dinding batur terdapat panil berbentuk bujursangkar berpola hias geometris. Pada teras makam terdapat dua nisan dari kayu persegi pipih.

Bangunan kedua memiliki ukuran 8,45 meter x 5 meter dengan tinggi 90 sentimeter. Berdiri diatas satu lapik. Pola hias tangga sama dengan bangunan pertama. Disini terdapat tiga makam, dua makam di sisi utara, dan satu makam di sisi selatan. Jirat makam di sisi selatan berbentuk persegi panjang. Nisan makam terbuat dari batu andesit, puncaknya berbentuk kurawal dengan ujung meruncing.

Bangunan ketiga adalah yang terbesar, memiliki ukuran 8,75 meter x 9 meter. Memiliki teras berukuran 12,5 meter x 11,5 meter. Hiasan bangunan utama berupa ukiran bunga dan geometris. Pada teras hiasannya berupa sulur. Diatas bangunan terdapat tiga nisan makam yang bentuknya sama dengan bangunan kedua.