Kesultanan Kutai atau lebih lengkap disebut Kesultanan Kutai Kartanegara ing Martadipura (Martapura) merupakan kesultanan bercorak Islam yang berdiri pada tahun 1300 oleh Aji Batara Agung Dewa Sakti di Kutai Lama dan berakhir pada 1960. Kemudian pada tahun 1999 kembali eksis di Kalimantan Timur setelah dihidupkan lagi pada tahun 2001 oleh Pemerintah Kabupaten Kutai Kartanegara sebagai upaya untuk melestarikan budaya dan adat Kutai Keraton.

Dihidupkannya kembali Kesultanan Kutai ditandai dengan dinobatkannya sang pewaris tahta yakni putera mahkota Aji Pangeran Prabu Anum Surya Adiningrat menjadi Sultan Kutai Kartanegara ing Martadipura dengan gelar H. Adji Mohamad Salehoeddin II pada tanggal 22 September 2001.

Kerajaan Kutai Kartanegara berdiri pada awal abad ke-13 di daerah yang bernama Tepian Batu atau Kutai Lama (kini menjadi sebuah desa di wilayah Kecamatan Anggana) dengan rajanya yang pertama yakni Aji Batara Agung Dewa Sakti (1300-1325). Kerajaan ini disebut dengan nama Kerajaan Tanjung Kute dalam Kakawin Nagarakretagama, yaitu salah satu daerah taklukan di negara bagian Pulau Tanjungnagara oleh Patih Gajah Mada dari Majapahit.

Menurut Hikayat Banjar dan Kotawaringin, negeri Kutai merupakan salah satu tanah di atas angin (sebelah utara) yang mengirim upeti kepada Maharaja Suryanata, raja Banjar-Hindu (Negara Dipa) pada abad ke-14. Pada pertengahan abad ke-17 Sultan Makassar (Gowa-Tallo) meminjam Pasir serta Kutai, Berau dan Karasikan (Kepulauan Sulu/Suku Suluk) sebagai tempat berdagang kepada Sultan Banjar IV Mustain Billah/Marhum Panembahan pada waktu Kiai Martasura diutus ke Makassar dan mengadakan perjanjian dengan I Mangadacinna Daeng Sitaba Karaeng Pattingalloang yaitu Sultan Tallo yang menjabat mangkubumi bagi Sultan Malikussaid Raja Gowa tahun 1638-1654.

Sejak tahun 1636, Kutai diklaim oleh Kesultanan Banjar sebagai salah satu vazalnya karena Banjarmasin sudah memiliki kekuatan militer yang memadai untuk menghadapi serangan Kesultanan Mataram yang berambisi menaklukan seluruh Kalimantan dan sudah menduduki wilayah Sukadana (1622). Sebelumnya Banjarmasin merupakan vazal Kesultanan Demak (penerus Majapahit), tetapi semenjak runtuhnya Demak, Banjarmasin tidak lagi mengirim upeti kepada pemerintahan di Jawa. Pada 1765, VOC membantu Sultan Banjar Tamjidullah I untuk menaklukan Kutai kembali dalam perjanjian 20 Oktober 1756.

Pada tahun 1787 Banjarmasin (serta vazalnya) menjadi daerah protektorat VOC. Hindia-Belanda diserahkan kepada Inggris karena kalah dalam peperangan. Belanda kembali datang ke Kalimantan (Banjarmasin) dan kemudian membuat perjanjian dengan Sultan Banjar. Pada tahun 1817, negeri Kutai diserahkan sebagai daerah pendudukan Hindia Belanda dalam Kontrak Persetujuan Karang Intan I pada 1 Januari 1817 antara Sultan Sulaiman dari Banjar dengan Hindia Belanda diwakili Residen Aernout van Boekholzt. Perjanjian berikutnya pada tahun 1823, negeri Kutai diserahkan menjadi daerah pendudukan Hindia Belanda dalam Kontrak Persetujuan Karang Intan II pada 13 September 1823 antara Sultan Sulaiman dari Banjar dengan Hindia Belanda diwakili Residen Mr. Tobias.

Negeri Kutai ditegaskan kembali termasuk daerah-daerah pendudukan Hindia Belanda di Kalimantan menurut Perjanjian Sultan Adam al-Watsiq Billah dengan Hindia Belanda yang ditandatangani dalam loji Belanda di Banjarmasin pada tanggal 4 Mei 1826 atau 26 Ramadhan 1241 H.

Pada abad ke-16, Kerajaan Kutai Kartanegara dibawah pimpinan raja Aji Pangeran Sinum Panji Mendapa berhasil menaklukkan Kerajaan Kutai (atau disebut pula: Kerajaan Kutai Martadipura atau Kerajaan Kutai Martapura atau Kerajaan Mulawarman) yang terletak di Muara Kaman. Raja Kutai Kartanegara pun kemudian menamakan kerajaannya menjadi Kerajaan Kutai Kartanegara Ing Martadipura sebagai peleburan antara dua kerajaan tersebut.

Pada abad ke-17, agama Islam yang disebarkan Tuan Tunggang Parangan diterima dengan baik oleh Kerajaan Kutai Kartanegara yang saat itu dipimpin Aji Raja Mahkota Mulia Alam. Setelah beberapa puluh tahun, sebutan Raja diganti dengan sebutan Sultan. Sultan Aji Muhammad Idris (1735-1778) merupakan sultan Kutai Kartanegara pertama yang menggunakan nama Islami. Dan kemudian sebutan kerajaan pun berganti menjadi Kesultanan Kutai Kartanegara ing Martadipura.

Sultan Aji Muhammad Idris yang merupakan menantu dari Sultan Wajo La Madukelleng berangkat ke tanah Wajo, Sulawesi Selatan untuk turut bertempur melawan VOC bersama rakyat Bugis. Pemerintahan Kesultanan Kutai Kartanegara untuk sementara dipegang oleh Dewan Perwalian.

Pada tahun 1739, Sultan Aji Muhammad Idris gugur di medan laga. Sepeninggal Sultan Idris, terjadilah perebutan tahta kerajaan oleh Aji Kado. Putera mahkota kerajaan Aji Imbut yang saat itu masih kecil kemudian dilarikan ke Wajo. Aji Kado kemudian meresmikan namanya sebagai Sultan Kutai Kartanegara dengan menggunakan gelar Sultan Aji Muhammad Aliyeddin.

Setelah dewasa, Aji Imbut sebagai putera mahkota yang syah dari Kesultanan Kutai Kartanegara kembali ke tanah Kutai. Oleh kalangan Bugis dan kerabat istana yang setia pada mendiang Sultan Idris, Aji Imbut dinobatkan sebagai Sultan Kutai Kartanegara dengan gelar Sultan Aji Muhammad Muslihuddin. Penobatan Sultan Muslihuddin ini dilaksanakan di Mangkujenang. Sejak itu dimulailah perlawanan terhadap Aji Kado.

Perlawanan berlangsung dengan siasat embargo yang ketat oleh Mangkujenang terhadap Pemarangan. Armada bajak laut Sulu terlibat dalam perlawanan ini dengan melakukan penyerangan dan pembajakan terhadap Pemarangan. Tahun 1778, Aji Kado meminta bantuan VOC namun tidak dapat dipenuhi.

Pada tahun 1780, Aji Imbut berhasil merebut kembali ibukota Pemarangan dan secara resmi dinobatkan sebagai sultan dengan gelar Sultan Aji Muhammad Muslihuddin di istana Kesultanan Kutai Kartanegara. Aji Kado dihukum mati dan dimakamkan di Pulau Jembayan.

Aji Imbut dengan gelar Sultan Aji Muhammad Muslihuddin memindahkan ibukota Kesultanan Kutai Kartanegara ke Tepian Pandan pada tanggal 28 September 1782. Perpindahan ini dilakukan untuk menghilangkan pengaruh kenangan pahit masa pemerintahan Aji Kado dan Pemarangan dianggap telah kehilangan tuahnya. Nama Tepian Pandan kemudian diubah menjadi Tangga Arung yang berarti Rumah Raja, lama-kelamaan Tangga Arung lebih populer dengan sebutan Tenggarong dan tetap bertahan hingga kini.

Pada tahun 1838, Kesultanan Kutai Kartanegara dipimpin oleh Sultan Aji Muhammad Salehuddin setelah Aji Imbut mangkat pada tahun tersebut.

Pada tahun 1844, 2 buah kapal dagang pimpinan James Erskine Murray asal Inggris memasuki perairan Tenggarong. Murray datang ke Kutai untuk berdagang dan meminta tanah untuk mendirikan pos dagang serta hak eksklusif untuk menjalankan kapal uap di perairan Mahakam. Namun Sultan A.M. Salehuddin mengizinkan Murray untuk berdagang hanya di wilayah Samarinda saja. Murray kurang puas dengan tawaran Sultan ini. Setelah beberapa hari di perairan Tenggarong, Murray melepaskan tembakan meriam ke arah istana dan dibalas oleh pasukan kerajaan Kutai. Pertempuran pun tak dapat dihindari. Armada pimpinan Murray akhirnya kalah dan melarikan diri menuju laut lepas. Lima orang terluka dan tiga orang tewas dari pihak armada Murray, dan Murray sendiri termasuk diantara yang tewas tersebut.

Insiden pertempuran di Tenggarong ini sampai ke pihak Inggris. Sebenarnya Inggris hendak melakukan serangan balasan terhadap Kutai, namun ditanggapi oleh pihak Belanda bahwa Kutai adalah salah satu bagian dari wilayah Hindia Belanda dan Belanda akan menyelesaikan permasalahan tersebut dengan caranya sendiri. Kemudian Belanda mengirimkan armadanya dibawah komando t'Hooft dengan membawa persenjataan yang lengkap. Setibanya di Tenggarong, armada t'Hooft menyerang istana Sultan Kutai. Sultan Aji Muhammad Salehuddin diungsikan ke Kota Bangun. Panglima perang kerajaan Kutai, Awang Long yang bergelar Pangeran Senopati bersama pasukannya dengan gagah berani bertempur melawan armada t'Hooft untuk mempertahankan kehormatan Kerajaan Kutai Kartanegara. Awang Long gugur dalam pertempuran yang kurang seimbang tersebut dan Kesultanan Kutai Kartanegara akhirnya kalah dan takluk pada Belanda.

Pada tanggal 11 Oktober 1844, Sultan A.M. Salehuddin harus menandatangani perjanjian dengan Belanda yang menyatakan bahwa Sultan mengakui pemerintahan Hindia Belanda dan mematuhi pemerintah Hindia Belanda di Kalimantan yang diwakili oleh seorang Residen yang berkedudukan di Banjarmasin.

Tahun 1846, H. von Dewall menjadi administrator sipil Belanda yang pertama di pantai timur Kalimantan. Pada tahun 1850, Sultan A.M. Sulaiman memegang tampuk kepemimpinan Kesultanan Kutai kartanegara Ing Martadipura. Pada tahun 1853, pemerintah Hindia Belanda menempatkan J. Zwager sebagai Assisten Residen di Samarinda. Saat itu kekuatan politik dan ekonomi masih berada dalam genggaman Sultan A.M. Sulaiman (1850-1899). Pada tahun 1863, kerajaan Kutai Kartanegara kembali mengadakan perjanjian dengan Belanda. Dalam perjanjian itu disepakati bahwa Kerajaan Kutai Kartanegara menjadi bagian dari Pemerintahan Hindia Belanda.

Tahun 1888, pertambangan batubara pertama di Kutai dibuka di Batu Panggal oleh insinyur tambang asal Belanda, J.H. Menten. Menten juga meletakkan dasar bagi eksploitasi minyak pertama di wilayah Kutai. Kemakmuran wilayah Kutai pun nampak semakin nyata sehingga membuat Kesultanan Kutai Kartanegara menjadi sangat terkenal di masa itu. Royalti atas pengeksloitasian sumber daya alam di Kutai diberikan kepada Sultan Sulaiman.

Tahun 1899, Sultan Sulaiman wafat dan digantikan putera mahkotanya Aji Mohammad dengan gelar Sultan Aji Muhammad Alimuddin.

Pada tahun 1907, misi Katolik pertama didirikan di Laham, Kutai Barat. Setahun kemudian, wilayah hulu Mahakam ini diserahkan kepada Belanda dengan kompensasi sebesar 12.990 Gulden per tahun kepada Sultan Kutai Kartanegara.

Sultan Alimuddin hanya bertahta dalam kurun waktu 11 tahun saja, beliau wafat pada tahun 1910. Berhubung pada waktu itu putera mahkota Aji Kaget masih belum dewasa, tampuk pemerintahan Kesultanan Kutai Kartanegara kemudian dipegang oleh Dewan Perwalian yang dipimpin oleh Aji Pangeran Mangkunegoro.

Pada tanggal 14 Nopember 1920, Aji Kaget dinobatkan sebagai Sultan Kutai Kartanegara dengan gelar Sultan Aji Muhammad Parikesit namun hal ini juga banyak mengalami kontroversi karena ada beberapa kerabat tidak setuju dengan pengangkatan Aji Muhammad Parikesit Tersebut, hal ini dikarenakan anggapan bahwa Aji Pangeran Soemantri 1 lah yang berhak diangkat menjadi Sultan Kutai. dalam beberapa media juga di sebutkan bahwa pengangkatan Aji Muhamad Parikesit dikarenakan ke dua saudaranya telah meninggal. Hal inilah yang mengundang banyak kontroversi dari berbagai pihak.

Sejak awal abad ke-20, ekonomi Kutai berkembang dengan sangat pesat sebagai hasil pendirian perusahaan Borneo-Sumatra Trade Co. Di tahun-tahun tersebut, kapital yang diperoleh Kutai tumbuh secara mantap melalui surplus yang dihasilkan tiap tahunnya. Hingga tahun 1924, Kutai telah memiliki dana sebesar 3.280.000 Gulden - jumlah yang sangat fantastis untuk masa itu.

Tahun 1936, Sultan A.M. Parikesit mendirikan istana baru yang megah dan kokoh yang terbuat dari bahan beton. Dalam kurun waktu satu tahun, istana tersebut selesai dibangun.

Ketika Jepang menduduki wilayah Kutai pada tahun 1942, Sultan Kutai harus tunduk pada Tenno Heika, Kaisar Jepang. Jepang memberi Sultan gelar kehormatan Koo dengan nama kerajaan Kooti.

Indonesia merdeka pada tahun 1945. Dua tahun kemudian, Kesultanan Kutai Kartanegara dengan status Daerah Swapraja masuk ke dalam Federasi Kalimantan Timur bersama-sama daerah Kesultanan lainnya seperti Bulungan, Sambaliung, Gunung Tabur dan Pasir dengan membentuk Dewan Kesultanan. Kemudian pada 27 Desember 1949 masuk dalam Republik Indonesia Serikat.

Daerah Swapraja Kutai diubah menjadi Daerah Istimewa Kutai yang merupakan daerah otonom/daerah istimewa tingkat kabupaten berdasarkan UU Darurat No.3 Th.1953.

Pada tahun 1959, berdasarkan UU No. 27 Tahun 1959 tentang "Pembentukan Daerah-Daerah Tingkat II di Kalimantan", wilayah Daerah Istimewa Kutai dipecah menjadi 3 Daerah Tingkat II, yakni:

Pada tanggal 20 Januari 1960, bertempat di Gubernuran di Samarinda, A.P.T. Pranoto yang menjabat sebagai Gubernur Kalimantan Timur, dengan atas nama Menteri Dalam Negeri Republik Indonesia melantik dan mengangkat sumpah 3 kepala daerah untuk ketiga daerah swatantra tersebut, yakni:

Sehari kemudian, pada tanggal 21 Januari 1960 bertempat di Balairung Keraton Sultan Kutai, Tenggarong diadakan Sidang Khusus DPRD Daerah Istimewa Kutai. Inti dari acara ini adalah serah terima pemerintahan dari Kepala Kepala Daerah Istimewa Kutai, Sultan Aji Muhammad Parikesit kepada Aji Raden Padmo sebagai Bupati Kepala Daerah Tingkat II Kutai, Kapten Soedjono (Walikota Samarinda) dan A.R. Sayid Mohammad (Walikota Balikpapan). Pemerintahan Kesultanan Kutai Kartanegara dibawah Sultan Aji Muhammad Parikesit berakhir, dan beliau pun hidup menjadi rakyat biasa.

Pada tahun 1999, Bupati Kutai Kartanegara, Syaukani Hasan Rais berniat untuk menghidupkan kembali Kesultanan Kutai Kartanegara ing Martadipura. Dikembalikannya Kesultanan Kutai ini bukan dengan maksud untuk menghidupkan feodalisme di daerah, namun sebagai upaya pelestarian warisan sejarah dan budaya Kerajaan Kutai sebagai kerajaan tertua di Indonesia. Selain itu, dihidupkannya tradisi Kesultanan Kutai Kartanegara adalah untuk mendukung sektor pariwisata Kalimantan Timur dalam upaya menarik minat wisatawan nusantara maupun mancanegara.

Pada tanggal 7 Nopember 2000, Bupati Kutai Kartanegara bersama Putera Mahkota Kutai H. Aji Pangeran Praboe Anoem Soerja Adiningrat menghadap Presiden RI Abdurrahman Wahid di Bina Graha Jakarta untuk menyampaikan maksud diatas. Presiden Wahid menyetujui dan merestui dikembalikannya Kesultanan Kutai Kartanegara kepada keturunan Sultan Kutai yakni putera mahkota H. Aji Pangeran Praboe.

Pada tanggal 22 September 2001, Putra Mahkota Kesultanan Kutai Kartanegara, H. Aji Pangeran Praboe Anoem Soerya Adiningrat dinobatkan menjadi Sultan Kutai Kartanegara dengan gelar Sultan H. Aji Muhammad Salehuddin II. Penabalan H.A.P. Praboe sebagai Sultan Kutai Kartanegara baru dilaksanakan pada tanggal 22 September 2001.

Pada masa kejayaannya hingga tahun 1959, Kesultanan Kutai Kartanegara ing Martadipura memiliki wilayah kekuasaan yang sangat luas. Wilayah kekuasaannya meliputi beberapa wilayah otonom yang ada di propinsi Kalimantan Timur saat ini, yakni:

Dengan demikian, luas dari wilayah Kesultanan Kutai Kartanegara hingga tahun 1959 adalah seluas 94.700 km2.

Pada tahun 1959, wilayah Kesultanan Kutai Kartanegara atau Daerah Istimewa Kutai dibagi menjadi 3 wilayah Pemerintah Daerah Tingkat II, yakni Kabupaten Kutai, Kotamadya Balikpapan dan Kotamadya Samarinda. Dan sejak itu berakhirlah pemerintahan Kesultanan Kutai Kartanegara setelah disahkannya Pemerintah Daerah Tingkat II Kabupaten Kutai melalui UU No.27 Tahun 1959 tentang Pencabutan Status Daerah Istimewa Kutai.

Dokumentasi bentuk istana Sultan Kutai hanya ada pada masa pemerintahan Sultan A.M. Sulaiman yang kala itu beribukota di Tenggarong, setelah para penjelajah Eropa melakukan ekspedisi ke pedalaman Mahakam pada abad ke-18. Carl Bock, seorang penjelajah berkebangsaan Norwegia yang melakukan ekspedisi Mahakam pada tahun 1879 sempat membuat ilustrasi pendopo istana Sultan A.M. Sulaiman. Istana Sultan Kutai pada masa itu terbuat dari kayu ulin dengan bentuk yang cukup sederhana.

Setelah Sultan Sulaiman wafat pada tahun 1899, Kesultanan Kutai Kartanegara kemudian dipimpin oleh Sultan A.M. Alimuddin (1899-1910). Sultan Alimuddin mendiami keraton baru yang terletak tak jauh dari bekas keraton Sultan Sulaiman. Keraton Sultan Alimuddin ini terdiri dari dua lantai dan juga terbuat dari kayu ulin (kayu besi). Keraton ini dibangun menghadap sungai Mahakam. Hingga Sultan A.M. Parikesit naik tahta pada tahun 1920, keraton ini tetap digunakan dalam menjalankan roda pemerintahan kerajaan.

Pada tahun 1936, keraton kayu peninggalan Sultan Alimuddin ini dibongkar karena akan digantikan dengan bangunan beton yang lebih kokoh. Untuk sementara waktu, Sultan Parikesit beserta keluarga kemudian menempati keraton lama peninggalan Sultan Sulaiman. Pembangunan keraton baru ini dilaksanakan oleh HBM ( Hollandsche Beton Maatschappij ) Batavia dengan arsiteknya Estourgie. Dibutuhkan waktu satu tahun untuk menyelesaikan istana ini. Setelah fisik bangunan keraton rampung pada tahun 1937, baru setahun kemudian yakni pada tahun 1938 keraton baru ini secara resmi didiami oleh Sultan Parikesit beserta keluarga. Peresmian keraton yang megah ini dilaksanakan cukup meriah dengan disemarakkan pesta kembang api pada malam harinya. Sementara itu, dengan telah berdirinya keraton baru maka keraton buruk peninggalan Sultan Sulaiman kemudian dirobohkan. Pada masa sekarang, areal bekas keraton lama ini telah diganti dengan sebuah bangunan baru yakni gedung Serapo LPKK.

Setelah pemerintahan Kesultanan Kutai berakhir pada tahun 1960, bangunan keraton dengan luas 2.270 m2 ini tetap menjadi tempat kediaman Sultan A.M. Parikesit hingga tahun 1971. Keraton Kutai kemudian diserahkan kepada Pemerintah Provinsi Kalimantan Timur pada tanggal 25 Nopember 1971. Pada tanggal 18 Februari 1976, Pemerintah Provinsi Kalimantan Timur menyerahkan bekas keraton Kutai Kartanegara ini kepada Departemen Pendidikan dan Kebudayaan untuk dikelola menjadi sebuah museum negeri dengan nama Museum Mulawarman. Didalam museum ini disajikan beraneka ragam koleksi peninggalan kesultanan Kutai Kartanegara, diantaranya singgasana, arca, perhiasan, perlengkapan perang, tempat tidur, seperangkat gamelan, koleksi keramik kuno dari China, dan lain-lain.

Dalam lingkungan keraton Sultan Kutai terdapat makam raja dan keluarga kerajaan Kutai Kartanegara. Jirat atau nisan Sultan dan keluarga kerajaan ini kebanyakan terbuat dari kayu besi yang dapat tahan lama dengan tulisan huruf Arab yang diukir. Sultan-sultan yang dimakamkan disini diantaranya adalah Sultan Muslihuddin, Sultan Salehuddin, Sultan Sulaiman dan Sultan Parikesit. Hanya Sultan Alimuddin saja yang tidak dimakamkan di lingkungan keraton, beliau dimakamkan di tanah miliknya di daerah Gunung Gandek, Tenggarong.

Pada tanggal 22 September 2001, putra mahkota H. Aji Pangeran Praboe Anum Surya Adiningrat dinobatkan menjadi Sultan Kutai Kartanegara dengan gelar Sultan H.A.M. Salehuddin II. Dipulihkannya kembali Kesultanan Kutai Kartanegara ini adalah sebagai upaya untuk melestarikan warisan budaya Kerajaan Kutai sebagai kerajaan tertua di Indonesia agar tak punah dimakan masa. Pemerintah Kabupaten Kutai Kartanegara telah membangun sebuah istana baru yang disebut Kedaton bagi Sultan Kutai Kartanegara yang sekarang. Bentuk kedaton baru yang terletak disamping Masjid Jami' Aji Amir Hasanuddin ini memiliki konsep rancangan yang mengacu pada bentuk keraton Kutai pada masa pemerintahan Sultan Alimuddin.

Dalam Kesultanan Kutai Kartanegara Ing Martadipura, gelar kebangsawanan yang digunakan oleh keluarga kerajaan adalah Aji. Gelar Aji diletakkan di depan nama anggota keluarga kerajaan. Dalam gelar kebangsawanan Kutai Kartanegara dikenal penggunaan gelar sebagai berikut:

Jika pria Aji menikah dengan wanita dari kalangan bangsawan Kutai sendiri atau dari kalangan rakyat biasa maupun suku lain, maka putra-putrinya berhak menyandang gelar Aji. Namun jika wanita Aji menikah dengan pria yang bukan keturunan bangsawan Kutai, maka putra-putrinya tidak dapat memperoleh gelar Aji, kecuali jika wanita Aji tersebut menikah dengan bangsawan keturunan Arab (Sayid).

Jika wanita Aji menikah dengan keturunan Arab (Sayid), maka putra-putrinya memperoleh gelar sebagai berikut:

Gelar Aji Sayid maupun Aji Syarifah tetap setara dengan gelar Aji biasa. Artinya gelar ini tetap dibawah Aji Bambang maupun Aji Raden.