Semula kota ini bernama '''Tepian Pandan''' ketika Aji Imbut memindahkan ibukota kerajaan dari [[Jembayan, Loa Kulu, Kutai Kartanegara|Pemarangan]]. Oleh Sultan Kutai, nama Tepian Pandan kemudian diubah menjadi [[Tangga Arung]] yang berarti rumah raja. Namun pada perkembangannya, Tangga Arung lebih populer dengan sebutan "Tenggarong" hingga saat ini.
Menurut tradisilegenda Orang Dayak Benuaq dari kelompok ''Ningkah Olo'', nama/kata Tenggarong menurut bahasa Dayak Orang Benuaq adalah "''Tengkarukng''" berasal dari kata ''tengkaq'' dan ''bengkarukng'', ''tengkaq'' berarti naik atau menjejakkan kaki ke tempat yang lebih tinggi (seperti meniti anak tangga), ''bengkarukng'' adalah sejenis tanaman akar-akaran. Menurut Orang Benuaq ketika sekolompok orang Benuaq (mungkin keturunan Ningkah Olo) menyusuri Sungai Mahakam menuju pedalaman mereka singgah di suatu tempat dipinggir tepian Mahakam, dengan menaiki tebing sungai Mahakam melalui akar bengkarukng, itulah sebabnya disebut ''Tengkarukng'' oleh aksen Melayu kadang "keseleo" disebut ''Tengkarong'', lama-kelamaan penyebutan tersebut berubah menjadi Tenggarong. sesuaiPerubahan aksentersebut disebabkan Bahasa Benuaq banyak memiliki konsonan yang sulit diucapkan oleh penutur yang biasa berbahasa Melayu/Indonesia.
