Persiba Balikpapan telah berdiri pada tahun 1950. Klub ini berjuluk Beruang Madu, hewan endemik yang juga menjadi maskot Balikpapan. Sebelumnya Persiba terlebih dulu kerap dijuluki Tim Selicin Minyak.
Pasang surut prestasi juga dialami tim ini dengan sekali turun kasta di Divisi Satu, yakni pada musim 1998-99. Lima musim bergelut di level kedua kompetisi sepak bola nasional, Persiba baru bisa kembali ke divisi utama setelah mampu menempati peringkat empat wilayah Timur pada musim kompetisi 2004.
Pada musim 2017 klub kebanggaan Balikpapan yaitu Persiba Balikpapan harus rela turun kasta ke Liga 2 karena masuk zona degradasi yaitu diposisi ke-17. Hingga saat ini Persiba Balikpapan masih berjuang untuk kembali ke kasta tertinggi Indonesia yaitu Liga 1.
Sampai tahun 2023, Persiba Balikpapan masih berkompetisi di Liga 2. Ditengah perjalanan tahun 2024 yang sebelumnya klub ini dipegang Gede Widiade karena prestasi yang kurang bagus akhirnya diserahkan kepada CEO Baru dengan kondisi yang sangat memprihatinkan alias terseok dengan tujuan menyelamatkan Persiba degradasi ke Liga 3, Alhasil kurang beruntung yang sebelumnya tim dikelola dengan apa adanya pemain. Dan akhirnya Persiba Balikpapan degradasi ke Liga 3 untuk kompetisi 2024/2025 nanti.
Stadion Persiba (atau juga dikenal dengan Stadion Parikesit( ini dipergunakan untuk menggelar pertandingan - pertandingan sepak bola dan merupakan markas dari Persiba Balikpapan. Stadion ini mampu menampung 10.000 orang. Untuk mendukung jalan Persiba dalam Liga Super 2008, stadion ini akan mengalami renovasi dan kapasitasnya diprediksi mampu mencapai 15.000 orang.
Pada tanggal 22 Agustus 2017, Persiba Balikpapan terakhir kalinya menggelar pertandingan di Stadion Parikesit saat menjamu PS TNI, pada saat itu Persiba Balikpapan berhasil memenangkan laga dengan skor 1-0, gol dicetak oleh Anmar Almubaraki pada menit terakhir pertandingan.
Kini stadion yang telah menemani Persiba Balikpapan puluhan tahun tersebut telah diambil alih oleh Pertamina sebagai pemilik aset.
Stadion ini selesai dibangun pada tahun 2017. Stadion Batakan memiliki 40.000 kapasitas penonton.
Stadion Batakan pertama kali digunakan oleh Persiba Balikpapan pada tanggal 9 September 2017 dalam lanjutan Liga 1. Pada saat itu Persiba Balikpapan berhasil mengamankan 3 poin dari lawannya yaitu Persegres Gresik United dengan skor 3-0.
