Menilik dari susunannya, kata “Balikpapan” dapat dimasukkan ke dalam asal kata bahasa Melayu. Konon, ada empat hikayat populer yang mengungkap asal-usul kota yang berada di pesisir timur Kalimantan ini.
PERTAMA, diceritakan bahwa pada 1739, Sultan Muhammad Idris dari Kerajaan Kutai memerintahkan kepada para pemukim di sepanjang Teluk Balikpapan untuk menyumbang bahan bangunan untuk pembangunan istana baru di Kutai Lama. Sumbangan tersebut berupa penyerahan 1.000 lembar papan yang diikat menjadi sebuah rakit dan dibawa ke Kutai Lama melalui sepanjang pantai.
Ternyata dalam perjalanannya, ada 10 keping papan yang terlepas dan hanyut hingga ke sebuah tempat yang kini bernama “Jenebora”. Dalam peristiwa ini, masyarakat dari suku Kutai menyebutnya dengan istilah “Balikpapan tu” atau “Baliklah papan itu”. Kemudian hari dikenal dengan sebutan Balikpapan.
Kedua, diceritakan dari masyarakat Suku Paser Balik. Lazim disebut Suku Paser Kuleng. Pada 1527, secara turun menurun, dihikayatkan tentang asal mula nama “Negeri Balikpapan”. Masyarakat Suku Paser Balik yang bermukim di sepanjang pantai teluk Balikpapan berasal dari keturunan kakek dan nenek yang bernama Kayun Kuleng dan Papan Ayun. Oleh keturunan kampung nelayan yang terletak di Teluk Balikpapan, wilayah tersebut diberi nama “Kuleng–Papan” atau artinya “Balik–Papan”.

Ketiga asal-usul nama Balikpapan bersumber cerita dari seorang. Ia yang dilepas oleh sang ayah yang tak lain adalah seorang raja. Keputusan itu dilakukan sang ayah lantaran tidak ingin putrinya jatuh ketangan musuh. Sang putri yang masih balita kemudian diikat di atas beberapa keping papan dalam keadaan terbaring. Lantaran terbawa arus dan diterpa gelombang, papan tersebut terbalik.
Papan tersebut kemudian terdampar di tepi pantai, lalu ditemukan oleh seorang nelayan. Ketika papan dibalik, ternyata terdapat seorang putri yang masih dalam keadaan terikat. Konon, putri tersebut bernama Petung yang berasal dari kerajaan Paser. Berdasarkan kejadian tersebut, lokasi ditemukannya sang putri dinamakan Balikpapan.
Keempat, diceritakan bahwa raja Aji Muhammad dari kerajaan Paser memberikan sebuah wilayah teluk kepada putrinya bernama Aji Tatin sebagai hadiah pernikahan dengan seorang bangsawan dari kerajaan Kutai. Sebagai penguasa wilayah, putri Aji Tatin memungut upeti berupa hasil bumi. Diantaranya kayu papan dari masyarakat di sepanjang teluk tersebut.
Pada suatu ketika kapal pengangkut upeti berupa papan kayu diterjang badai hebat. Ombak besar membuat kapal terbalik dan menghantam karang. Tidak seorangpun penumpang kapal yang merupakan pengikut setia Aji Tatin yang selamat. Untuk mengenang peristiwa tersebut, wilayah teluk tempat kapal pegangkut papan itu terbalik dinamakan Balikpapan. Sementara karang tempat kapal terhempas disebut Pulau Tukung, berasal dari kata “Tokong” atau “Galah” para pendayung yang patah.
Terlepas dari cerita mana yang benar, hal tersebut telah menjadi wujud kekayaan budaya dan sejarah Kota Balikpapan yang harus dilestarikan dari generasi ke generasi serta perlu diketahui oleh seluruh masyarakat Kota Balikpapan. (pelbagai sumber)