Sejarah Kesultanan Palembang dimulai pada pertengahan abad ke-15 pada masa hidupnya seorang tokoh bernama Ario Damar. Beliau adalah putra Raja Majapahit Prabu Kertabumi Brawijaya V terakhir, yang berkuasa tahun 1455-1486 di Palembang Lamo, yang sekarang letaknya di kawasan 1 Ilir.
Saat Ario Damar ke Palembang, penduduknya sudah banyak memeluk Islam dan ia juga kemudian memeluk Islam. Namanya pun berubah menjadi Ario Abdillah atau Ario Dillah. Ia mendapat hadiah dari ayahnya salah seorang isterinya keturunan Cina yang telah memeluk Islam. Saat putri ini diboyong ke Palembang ia sedang mengandung Raden Fatah.
Setelah Majapahit runtuh, Sunan Ampel sebagai wakil Wali Songo, mengangkat Raden Fatah menjadi penguasa seluruh Jawa menggantikan ayahnya. Atas bantuan dari daerah-daerah lainnya yang sudah lepas dari Majapahit seperti Jepara, Tuban, Gresik, Raden Fatah mendirikan Kerajaan Islam dengan Demak sebagai pusatnya (1481). Raden Fatah memperoleh gelar Senapati Jimbun Ngabdur-Rahman Panembahan Palembang Sayidin PanataGama.
Kondisi ini menempatkan Palembang menjadi wilayah perlindungan Kerajaan Demak sekitar tahun 1546. Namun kejayaan Kerajaan Demak tidak berlangsung lama, setelah Pangeran Trenggono Sultan Demak III, anak Raden Fatah wafat, terjadilah perang saudara yang melibatkan Aria Penangsang dari Jipang dan Pangeran Hadiwijaya dari Pajang (Badaruddin, 2008:8). Kematian Aria Penangsang membuat para pengikutnya, yakni orang-orang keturunan Pangeran Trenggono (atau Keturunan Raden Fatah) dari Kerajaan Demak ke Palembang.
Mereka berjumlah 80 kepala keluarga dan diketuai oleh Pangeran Sedo Ing Lautan (1547-1552) ini melarikan diri ke Palembang yang saat itu Palembang di bawah pimpinan Dipati Karang Widara, keturunan Demang Lebar Daun (Badaruddin, 2008:8). Mereka lalu membangun kekuatan baru dan mendirikan Kerajaan Palembang yang bercorak Islam dengan mendirikan Keraton Kuto Gawang yang pada saat ini situsnya tepat berada di kompleks PT. Pusri Palembang (Badaruddin, 2008:8).
Pada aspek hukum, di era ini, istri Pangeran Sedo Ing Kenayan Jamaludin Mangkurat IV (1639-1650), Ratu Sinuhun telah menyusun Undang-undang Simbur Cahaya yang mengatur adat pergaulan bujang gadis, adat perkawinan, piagam, dan lain sebagainya (Badaruddin, 2008:8). Namun pada masa ini juga, Gubernur Jendral di Batavia Jacob Specx (1629-1632) telah membuka Kantor perwakilan Dagang VOC (Factorij) di Palembang (Triyono, 2007).
Anthonij Boeij sejak tahun 1655 ditunjuk sebagai wakil pedagang VOC di Palembang namun tetap tinggal di kapal karena belum punya tempat (loji) di darat. Pembangunan loji dari batu mengalami kesulitan karena pada saat yang sama didirikan keraton di Beringin Janggut, Masjid Agung dan lainnya. Kemudian VOC menggantikannya dengan Cornelis Ockerz yang tadinya dicadangkan untuk perwakilan di Jambi.
Pada 22 Agustus 1658 beberapa bangsawan Palembang, yakni Putri Ratu Emas, Tumenggung Bagus Kuning Pangkulu, Pangeran Mangkubumi Nembing Kapal, dan Kiai Demang Kecek naik ke atas kapal yacht Belanda, Jacatra dan de Wachter, dan membunuh Ockerz dan 42 orang Belanda lainnya serta menawan 28 orang Belanda. Peristiwa ini terjadi karena kecurangan dan kelicikan Belanda.
Untuk membalas tindakan orang Palembang ini Belanda mengirimkan armadanya yang dipimpin Laksamana Johan Van der Laen pada tanggal 24 November 1659. Pada serangan ini, Belanda membakar habis Keraton Kuta Gawang beserta permukiman penduduk, termasuk pemukiman orang Cina, Portugis, Arab, dan bangsa-bangsa lain yang ada di seberang Kuta tersebut selama 3 hari 3 malam. Akibat Keraton Kuto Gawang dibakar habis oleh VOC, Sultan Abdurrahman kemudian memindahkan keraton ke Beringin Janggut (sekarang sebagai pusat perdagangan Palembang).
Kesultanan Palembang Darussalam sendiri secara resmi diproklamirkan oleh Pangeran Ratu Kimas Hindi Sri Susuhanan Abdurrahman Candiwalang Khalifatul Mukminin Sayidul Iman (atau lebih dikenal Ki Mas Hindi/Sunan Cinde Walang) sebagai sultan pertama (1659-1706), terlepas dari pengaruh Kerajaan Mataram (Jawa). Dia menyatakan diri sebagai sultan, setara dengan Sultan Agung di Mataram. Corak pemerintahannya pun diubah condong ke corak Melayu dan lebih disesuaikan dengan ajaran agama Islam.
Dari bentuk sistem pemerintahan keraton Jawa di tepi Sungai Musi, para penguasa Kerajaan Palembang ini kemudian beradaptasi dengan lingkungan Melayu di sekitarnya. Terjadilah suatu akulturasi dan asimilasi kebudayaan Jawa dan Melayu, yang kemudian dikenal sebagai kebudayaan Palembang.
Sultan Mahmud Badaruddin I yang bergelar Jayo Wikramo (1724-1757) adalah tokoh pembangunan era ini. Dia membuat kanal-kanal di wilayah kesultanan yang berfungsi ganda, yaitu sebagai alur pelayaran dan pertanian juga untuk pertahanan. SMB I memantapkan konsep kosmologi Batanghari Sembilan sebagai satu lifeworld dari kekuasaan Palembang.
Batanghari Sembilan adalah satu konsep Melayu - Jawa, yaitu adalah delapan penjuru angin yang terpencar dari pusatnya yang merupakan penjuru kesembilan. Pusat atau penjuru kesembilan ini berada di Keraton Palembang. Di masa kepemimpinannya juga, ia telah berhasil melakukan pembangunan, antara lain Gubah Kawah Tekurep (1728), Mesjid Agung (1738) dan Keraton Kuto Lamo (1737) (Badaruddin, 2008:33).
Tahun 1821 Keraton Kuto Lamo diserang oleh Belanda dan tanggal 7 Oktober 1823, Reguting Commisaris Belanda J.L Van Seven House diperintahkan membongkarnya habis untuk menghilangkan monumental Kesultanan Palembang demi membalas dendam atas dibakarnya loji Sungai Aur oleh SMB I pada tahun 1811. Bangunan ini dibangun kembali (1825) yang selanjutnya dijadikan komisariat Pemerintah Hindia Belanda untuk Sumatera Bagian Selatan sekaligus sebagai kantor Residen.
Pada tahun 1942-1945 gedung ini sempat dikuasai oleh Jepang. Tahun 1949 gedung tersebut dijadikan kantor Toritorium II Sriwijaya dan tahun 1960-1974 digunakan sebagai Resimen Induk IV Sriwijaya. Kini Keraton Kuto Lamo itu berganti nama menjadi Museum Sultan Mahmud Badaruddin II yang diabadikan sekaligus untuk mengingat dan menghargai jasa-jasanya.