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.<ref>[http://www.korem091asn.mil.id/profil/sejarah.html "Sejarah Korem 091/Aji Surya Natakesuma"]</ref> 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 tanggal 11 NopemberNovember 1985 Makorem dipindahkan ke [[Samarinda]].
