Keberadaan kerajaan Kutai diketahui berdasarkan sumber yang diketemukan diantaranya berupa prasasti berbentuk yupa (tiang batu) berjumlah tujuh buah. Kerajaan Kutai diperkirakan muncul pada abad ± 4 M dan merupakan salah satu kerajaan tertua di Nusantara. Hingga saat ini, sangat sedikit bukti yang diketemukan guna menelusuri sejarah dan keberadaan Kerajaan ini.
Nama Kutai diberikan oleh para ahli mengambil dari nama tempat ditemukannya prasasti yang menunjukkan eksistensi kerajaan tersebut. Belum ada informasi yang secara jelas menyebutkan nama kerajaan ini dan memang sangat sedikit informasi yang dapat diperoleh. Dari salah satu yupa yang menggunakan huruf Pallawa dan bahasa sansekerta tersebut, diketahui bahwa raja yang memerintah kerajaan Kutai saat itu adalah Mulawarman. Namanya dicatat dalam yupa karena kedermawanannya menyedekahkan 20.000 ekor sapi kepada kaum brahmana. Mulawarman diduga adalah anak Aswawarman dan cucu Kundungga. Nama Mulawarman dan Aswawarman sangat kental dengan pengaruh bahasa Sanskerta sedangkan Kundungga masih berbau lokal.
Raja Kudungga diduga adalah raja pertama yang berkuasa di Kerajaan Kutai. Akan tetapi, apabila dilihat dari nama raja yang masih meng-gunakan nama lokal, para ahli berpendapat bahwa pada masa pemerintahan Raja Kudungga pengaruh Hindu baru masuk ke wilayahnya. Kedudukan Raja Kudungga pada awalnya adalah seorang kepala suku. Dengan masuknya pengaruh Hindu, ia mengubah struktur pemerintahannya menjadi kerajaan dan mengangkat dirinya menjadi raja, sehingga pergantian raja dilakukan secara turun-temurun.
Aswawarman adalah raja yang pernah memerintah Kerajaan Kutai. Ia disebut sebagai Dewa Ansuman/Dewa Matahari Ia juga diketahui sebagai pendiri dinasti Kerajaan Kutai sehingga diberi gelar Wangsakerta, yang artinya pembentuk keluarga. Dalam yupa tersebut juga menyatakan bahwa Raja Aswawarman merupakan seorang raja yang cakap dan kuat. Pada masa pemerintahannya, wilayah kekuasaan Kutai diperluas lagi. Hal ini dibuktikan dengan pelaksanaan upacaraAsmawedha.
Informasi tentang upacara sejenis di dapat dari negeri India, pada masa pemerintahan Raja Samudragupta ketika ingin memperluas wilayahnya. Dalam upacara Asmawedha dilaksanakan pelepasan kuda dengan tujuan untuk menentukan batas kekuasaan Kerajaan Kutai. Dengan kata lain, sampai di mana ditemukan tapak kaki kuda, maka sampai di situlah batas Kerajaan Kutai. Pelepasan kuda-kuda itu diikuti oleh prajurit Kerajaan Kutai. Aswawarman sendiri memiliki tiga orang putera, dan salah satunya adalah Mulawarman.
Dalam kehidupan politik dari informasi yupa diketahui bahwa raja terbesar Kutai adalah Mulawarman. Kerajaan Kutai mengalami masa keemasan. Wilayah kekuasaannya meliputi hampir seluruh wilayah Kalimantan Timur.
Pada awal abad ke-13, berdirilah sebuah kerajaan baru di Tepian Batu atau Kutai Lama yang bernama Kerajaan Kutai Kartanegara dengan rajanya yang pertama, Aji Batara Agung Dewa Sakti (1300-1325).
Dengan adanya dua kerajaan di kawasan Sungai Mahakam ini tentunya menimbulkan friksi diantara keduanya. Pada abad ke-16 terjadilah peperangan diantara kedua kerajaan Kutai ini. Kerajaan Kutai Kartanegara dibawah rajanya Aji Pangeran Sinum Panji Mendapa akhirnya berhasil menaklukkan Kerajaan Kutai Martadipura. Raja kemudian menamakan kerajaannya menjadi Kerajaan Kutai Kartanegara Ing Martadipura.
Pada abad ke-17 agama Islam diterima dengan baik oleh Kerajaan Kutai Kartanegara. Selanjutnya banyak nama-nama Islami yang akhirnya digunakan pada nama-nama raja dan keluarga kerajaan Kutai Kartanegara. Sebutan raja pun diganti dengan sebutan Sultan. Sultan yang pertama kali menggunakan nama Islam adalah Sultan Aji Muhammad Idris (1735-1778).
Perlu diingat bahwa Kutai ini (Kutai Martadipura) berbeda dengan Kerajaan Kutai Kartanegara yang saat itu ibukota di Kutai Lama (Tanjung Kute).
Kutai Kartanegara inilah, di tahun 1365, yang disebutkan dalam sastra Jawa Negarakertagama.
