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.
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.
"sejarah korem 091/aji surya natakesuma" berdasarkan surat keputusan kasad : skep/ 6 / i / 1985 tanggal, 8 januari 1985 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 11 nopember 1985 makorem dipindahkan ke samarinda.
korem 091/aji surya natakesuma membawahi 7 satuan kewilayahan dan 2 satuan tempur yang tersebar di wilayah kalimantan timur, yakni:
kodim 0904/tanah grogot
kodim 0906/kutai kartanegara
kodim 0912/kutai barat
yonif 611/awang long, loa janan
yonif 614/raja pandhita, malinau.
sedangkan kodim 0905/balikpapan , yonif 612/modang , baterai b armed 16/tkp, den kav-1 (sekarang yonkav 13/satya lembuswana) serta den rudal 002/bontang walaupun berada di wilayah korem 091/aji surya natakesuma tetapi secara taktis dan administratif satuan ini langsung berada di bawah komando daerah militer vi/mulawarman.
kolonel czi soekardi (11 juni 1981 s.d. 1 sept 1983)
kolonel inf aryono (1 des 1983 s.d. 1 des 1984)
kolonel art harwin wasisto (1 des 1984 s.d. 31 okt 1986)
kolonel art harsono (31 okt 1986 s.d. 13 des 1988)
kolonel inf budi sujana (13 des 1988 s.d. 25 nop 1990)
kolonel inf r. adang ruchiatna puradiredja (3 jan 1991 s.d. 3 sep 1992)
kolonel inf e. imam maksudi (3 sep 1992 s.d. 11 peb 1994)
brigjen tni h. gunawan koswara (11 peb 1994 s.d. 18 mar 1995)
brigjen tni h. sutarjo (18 mart 1995 s.d. 16 nop 1996)
kolonel inf djali yusuf (16 nop 1996 s.d. 18 juni 1998)
kolonel art rudy landung b,s.ip (18 juni 1998 s.d. 28 jan 2000)
kolonel inf tri subagyo (28 jan 2000 s.d. 3 mei 2002)
brigjen tni hotma marbun (3 mei 2002 s.d. 14 jan 2004)
kolonel inf h. amreyza anwar,s.ip (14 jan 2004 s.d. 16 maret 2005)
kolonel inf hadi suharto (16 mart 2005 s.d. 28 des 2005)
kolonel inf bambang budi waluyo (28 des 2005 s.d 12 peb 2008)
kolonel inf h. ibrahim saleh, se (12 peb 2008 s.d. 26 juni 2009)
kolonel inf musa bangun (26 juni 2009 s.d. 28 juni 2010)
kolonel inf aries martanto (28 juni 2010 s.d. 26 sep 2011)
kolonel inf ganip warsito (26 september s.d 18 juni 2012)
korem 091/aji surya natakesuma di pimpin jenderal bintang satu "13 korem akan dipimpin bintang satu"
brigjen tni gadang pambudi (18 juni 2012 s.d 7 okt 2013)
brigjen tni nono suharsono (7 okt 2013 s.d 6 jan 2015)
brigjen tni teguh arief indratmoko (6 jan 2015 s.d 28 mei 2016)
brigjen tni makmur umar (28 mei 2016 s.d sekarang)