[[Berkas:Balikpapan-landing.jpg|ka|jmpl|Tentara [[Sekutu]] mendarat di Balikpapan, [[1 Juli]] [[1945]].]]
Daerah Balikpapan dan Balikpapan Seberang ([[Penajam]]) merupakan bagian dari wilayah negara dependen [[Kesultanan Kutai]].<ref>[http://www.indonesianhistory.info/map/borneozelfb1900.html Peta Native states (zelfbesturen) in Dutch Borneo, 1900]</ref><ref>[http://www.indonesianhistory.info/map/borneo1902.html Peta Administrative divisions in Dutch Borneo, 1902]</ref><ref>[http://www.indonesianhistory.info/map/borneo1930.html Peta Administrative divisions in Dutch Borneo, 1930 ]</ref> Tahun 1942 Penajam termasuk dalam wilayah Balikpapan.<ref>[http://www.indonesianhistory.info/map/borneo1942.html?zoomview=1 Peta Borneo in 1942 ]</ref> Sejak sekitar tahun [[1636]], Kalimantan pada umumnya termasuk [[Kesultanan Kutai|negara bagian Kutai]], [[Kesultanan Pasir|negara bagian Paser]] dan [[Kesultanan Berau|negara bagian Berau]] diklaim sebagai wilayah mandala negara [[Kesultanan Banjarmasin]].<ref>{{id}} {{cite book|url=http://books.google.co.id/books?id=TYYeAAAAMAAJ&q=sawakung&dq=sawakung&hl=id&ei=KLzPTfL6JIy3rAfs7rDCCg&sa=X&oi=book_result&ct=result&resnum=2&ved=0CDAQ6AEwAQ|title=Pengantar sejarah Indonesia baru, 1500-1900: Dari emporium sampai imperium|last=Kartodirdjo|first=Sartono|publisher=Gramedia|year=1993|isbn=9794031291|pages=121}}ISBN 978-979-403-129-2</ref> Pada [[131 AgustusJanuari]] [[17871817]], [[SunanSulaiman Natadari AlamBanjar]] telah menyerahkan kedaulatannya atas sebagian besar Kalimantan kepada perusahaan VOC, yang kemudian diperbarui lagi pada tanggal [[4 Mei]] [[1826]] pada masa [[Sultan Adam]]. Setelah itu Kalimantan pada umumnya menjadi wilayah negara [[Hindia Belanda]]. Tahun [[1844]], bekas negara bagian Kutai secara resmi mendapat pengakuan sebagai negara [[dependensi]] di dalam negara Hindia Belanda.<ref>{{en icon}} {{cite book|url=http://books.google.co.id/books?id=f9T74ges6DIC&lpg=PT31&dq=sultan%20sulaiman&pg=PT31#v=onepage&q=sultan%20sulaiman&f=true|title=East Kalimantan: The Decline of a Commercial Aristocracy|last=Magenda|first=Burhan Djabier|publisher=Equinox Publishing|year=2010|isbn=602-8397-21-0}}ISBN 978-602-8397-21-6</ref> Menurut Staatsblad van Nederlandisch Indië tahun 1849, Kutai termasuk dalam zuid-ooster-afdeeling berdasarkan ''Bêsluit van den Minister van Staat, Gouverneur-Generaal van Nederlandsch-Indie'', pada 27 Agustus 1849, No. 8<ref>{{nl icon}} {{cite journal|url=http://books.google.co.id/books?id=KJFBAAAAYAAJ&dq=Verdeeling%20van%20het%20Eiland%20Borneo%20in%20tteee%20%20afdeelingen%2C%20onder%20de%20benaming%20van%20Wester%20afdeeling%20en%20Zuid%20en%20Ooster%20afdeeling.&pg=PA55-IA22#v=onepage&q=Verdeeling%20van%20het%20Eiland%20Borneo%20in%20tteee%20%20afdeelingen,%20onder%20de%20benaming%20van%20Wester%20afdeeling%20en%20Zuid%20en%20Ooster%20afdeeling.&f=false |author=Nederlandisch Indië|title=Staatsblad van Nederlandisch Indië|publisher= s.n.|year=1849}}</ref> Tahun 1855, Kutai merupakan sebagian dari ''de zuid- en oosterafdeeling van Borneo'' yang beribu kota di Banjarmasin.<ref>{{nl}} {{cite book|pages=241|url=http://books.google.co.id/books?id=0GM-AAAAcAAJ&dq=tanah-koessan&pg=PA241#v=onepage&q&f=false|title=Bydragen tot de kennis van verschillende overzeesche landen, volken, enz|volume=1|author=J. B. J Van Doren|publisher=J. D. Sybrandi|year=1860}}</ref>
