[[Kabupaten Berau]] berasal dari [[Kesultanan Berau]] yang didirikan sekitar abatabadd XIVke-14. Menurut sejarah Berau, Raja pertama yang memerintah bernama [[Baddit DippatungDipattung]] dengan gelar ''Aji Raden Surya Nata Kesuma'' dan Isterinya bernama ''Baddit Kurindan'' dengan gelar ''Aji Permaisuri''. Pusat pemerintahan kerajaan pada awalnya berkedudukan di [[Sungai Lati, Sambaliung, Berau|Sungai Lati]] (sekarang menjadi lokasi pertambangan Batu Bara PT. Berau Coal).
[[Aji Raden Surya NataSuryanata Kesuma]] menjalankan masa pemerintahannya tahun [[1400]] – [[1432]] dengan adil dan bijaksana, sehingga kesejahteraan rakyatnya meningkat. Pada masa itu dia berhasil menyatukan wilayah pemukiman masyarakat Berau yang disebut [[Banua]], yaitu ''Banua Merancang'', ''Banua Pantai'', ''Banua Kuran'', ''Banua Rantau Buyut'' dan ''Banua Rantau Sewakung''.
Di samping kewibawaannya, kedudukan [[Aji Raden Surya NataSuryanata Kesuma]] juga sangat berpengaruh, menjadikan dia disegani lawan maupun kawan. Untuk mengenang jasa Raja Berau yang pertama ini, Pemerintah telah mengabdikannya sebagai nama Korem 091 Aji Raden Surya Nata Kesuma yang Rayon Militer Kodam VI/TPR.
Setelah beliau wafat, Pemerintahan [[Kesultanan Berau]] dilanjutkan oleh putranya dan selanjutnya secara turun temurun keturunannya memerintah sampai pada sekitar abad ke-17. Kemudian awal sekitar abad XVIII datanglah penjajah Belanda memasuki kerajaan Berau dengan berkedok sebagai pedagang (VOC). Namun kegiatan itu dilakukan dengan politik ''De Vide Et Impera'' (politik adu domba). Kelicikan Belanda berhasil memecah belah Kerajaan Berau, sehingga kerajaan terpecah menjadi 2 Kesultanan yaitu [[Kesultanan Sambaliung]] dan [[Kesultanan Gunung Tabur]].
