Raden Aji Surya Natakesuma adalah seorang Sultan yang berhasil menampilkan suatu kepemimpinan, di bidang pemerintahan dan sosial yang menyentuh denyut kehidupan rakyatnya. Dengan kepribadiannya yang disegani rakyatnya dan kerajaan tetangganya pada waktu itu, maka Raden Aji Surya Natakesuma dapat mempersatukan kedua daerah yaitu Berau dan Bulungan, kedalam suatu wadah yang memungkinkan berkembangnya pemerintahan yang adil dan berdaulat.
Sejarah
Pada awal pembentukannya, Korem ini secara taktis maupun administrasi berada di bawah kendali Kodam IX/Mulawarman yang bermarkas di Balikpapan. Sebagai markas sementara sebelum selesainya pembangunan markas Korem di Tarakan, dan selama pejabat Danrem belum ada, maka Pangdam IX/Mulawarman menunjuk Kasrem 091/ASN sebagai koordinatornya. Pada tanggal 2 Juni 1981 berdasarkan Sprin Pangdam IX/Mulawarman Nomor Sprin / 423-Spres/VI/1981, diangkatlah Kolonel Czi Sukardi sebagai Danrem yang pertama.[1] Berdasarkan Surat Keputusan Kasad: Skep/6/I/1985 tanggal, 8 Januari1985 maka Makorem diredislokasikan dari Tarakan ke Balikpapan. Terbentuknya Kodam VI/Tanjungpura sebagai satu-satunya sub kompartemen di Kalimantan sejak Mei 1985 maka secara otomatis status Korem 091/ASN beserta jajarannya menjadi organik dari Kodam VI/Tanjungpura, dan mulai tahun 1985, pada tanggal 11 November 1985 Makorem dipindahkan ke Samarinda.
Wilayah tugas
Korem 091/Aji Surya Natakesuma membawahi 9 satuan kewilayahan dan 1 satuan tempur yang tersebar di wilayah Kalimantan Timur dan di IKN Nusantara, yakni:
