Desa Malinau Kota awalnya merupakan sebuah kampong yang bernama Pagun Sembambon. Bambon adalah salah satu tanaman sejenis rotan yang biasa dipakai oleh maasyarakat Malinau tempo dulu untuk menganyam atau mengikat daun rumbia untuk atap rumah pada masa itu dan mayoritas suku atau etnis pada masa itu ialah Tidung dan Bulungan .

Tahun 1903 Panembahan Aji Kuning yang bernama  Aji Sahabudin mulai membuka hutan dikuala sungai Sebambon yang digunakan sebagai tempat berladang. Pada tahun 1910 penduduk semakin banyak yang pindah dari Kuala Kabiran ke Sebambon untuk ikut berladang dan membuat rumah, dan pada masa itu di jadikanlah perkampungan oleh masyarakat stempat yang dinamakan kampung Malinau. Nama Malinau diambil dari Bahasa Dayak Abai yang artinya “Mal’’ membuat, “Inau” sagu yang terbuat dari pohon Rumbia, dan pada masa itulah perumahan mulai diatur dan dalam 1 rumah dihuni oleh 7 orang sampai 10 kepala keluarga.

         Tahun 1911 jalanan mulai dibuat dengan parit di sisi kanan dan kiri agar tidak runtuh dibuatlah siring  dari papan ulin sepanjang kampung sebambon. Akhirnya Sebambon dijadikan perkampungan baru, yang diberi nama kampung Malinau Kota hal ini di karenakan perumahan dan jalan di buat rapi  menyerupai kota, jalan tersebut diberi nama jalan Panembahan, yang dikenal hingga sekarang.

Malinau Kota dalam beberapa perjalanan sejarahnya mengalami beberapa masa pemerintahan yaitu:

• Masa Pemerintahan berstatus Kampung yang dipimpim oeh seorang PEMBAKAL (1903 – 1923 ). Pembakal adalah sebutan untuk pejabat atau Kepala Kampung di masa pemerintah Kerajaan Bulungan Van Tidoeng. Diantara pejabatnya ialah:
  1. Panembahan Aji Kuning ( Jabatan Pembakal )
  2. Zainal Abidin ( Jabatan Pembakal II )
  3. Abdulah ( Jabatan Pembakal )
  4. Aji Kaharudin ( Jabatan Pembakal )
  5. Akiu ( Jabatan Pembakal )
  6. Aji Kapitan ( Jabatan Wamkil Pembakal )
  7. Aji Nata Jaya ( Jabatan Pembakal )
  8. Untung ( Jabatan Wakil Pembakal )
  9. S Berahim ( Jabatan Kepala Kampung )
  10. Sulaiman Abdulah ( Jabatan Kepala Kampung )
• Masa Pemerintahan berstatus Districk Schoof Malinau, pada masa perintahan kerajaan Bulungan Van Tidung, Malinau termasuk dalam Wilayah Districk Sesayap Duri. Yang dipakai oleh Datu Bestari sebagai Onder Districk Schoop Van Sesayap Duri. Dan kepala Districk pada masa itu di sebut Kyai ( 1923 – 1949 ) setelah pemerintahan distrik di pindahkan dari sesayap duri ke Malinau maka Kepala Districknya pada masa itu diantaranya ialah :

Sebelum Merdeka :

1. Datu Bestari yang turut mendampingi pangiran Muda Abdusamad yang bergelar Pangiran Maharajadinda dari sesayap Duri. pangeran Maharajadinda adalah Pembakal Sesayap Duri, beliau mengundurkan diri dari pembakal dan digantikan oleh adiknya yaitu Alung yang bergelar Pangiran Alung.
2. Gusti Abdurahman
3. Abdurahman
4. Haji Marwan
5. Anang Atjcil

Sesudah Merdeka :

1. Mustafa Bakri
2. Datu Belindungan
3. Ahmad Kusasi

•  Masa Pemerintahan berstastus Kewedanaan. Kepala Kewedaan biasanya di sebut dengan Wedana ( 1949 – 1964 ). Setelah status malinau berubah dari status Onder Districk Schoof  Malinau menjadi status Kewedanaan Tana Tidung wilayahnya Meliputi :

1. Wilaya Kerayan
2. Wilayah Mentarang
3. Wilaya Sebuku
4. Lumbis

Wedana Tana Tidung Pada Masa itu ialah :

1. Kusasi
2. Andi Tjatjo
3. Datu Badaruddin
4. Arsyad
5. Abdul Muis
6. Ibramsyah Zafri