Sejak awal beroperasinya Perusahaan Tambang Batubara PT. Kaltim Prima Coal (KPC) pada tahun 1990 kebutuhan akan layanan sekolah bagi putra putri karyawan begitu prioritas dan strategis. Kehadiran karyawan dan keluarganya ke Sangatta sebagai daerah yang baru dibuka, tentu memerlukan layanan pendidikan yang berkualitas dan memadahi. Sementara sekolah yang ada pada saat itu masih minim dan kurang memadahi, belum ada TK, SMP maupun SMA. Di sisi lain, KPC yang saat itu sedang gencar gencarnya merekrut banyak karyawan baru baik yang berasal dari Sangatta maupun luar daerah sebagai tenaga profesional. Setiap calon karyawan selalu menanyakan bagaimana dengan pendidikan putra-putrinya apabila mereka akan bertempat tinggal di Sangatta. Mereka mendesak perusahaan agar dibangunkan fasilitas dan layanan pendidikan yang memadahi bagi putra putrinya sehingga mereka dapat tenang bekerja. Dengan bantuan seorang Konsultan Pendidikan dari Balai Pendidikan Guru di Bandung yaitu Bapak Drs. Jusuf Djajadisastra dan Yayasan Perguruan Cikini Jakarta, di susunlah kerangka dasar berdirinya Yayasan Pendidikan Prima Sangatta Baru (YPPSB) sekolah khusus karyawan KPC di Sangatta.
Sekolah YPPSB baru diresmikan pada tanggal 13 Juli 1991 oleh Managing Director PT KPC, Dr. David Klingner dan Kepala Kantor Wilayah Departemen Pendidikan dan Kebudayaan (Depdikbud) Provinsi Kalimantan Timur, Drs. Amirudin Maula. Saat didirikan nama Yayasannya adalah Yayasan Pendidikan Prima Sangatta Baru yang kemudian sedikit berubah menjadi Yayasan Pendidikan Prima Swarga Bara (YPPSB) untuk mengelola operasional sekolah TK, SD dan SMP. Selama tiga tahun sejak berdiri, Sekolah YPPSB dibimbing oleh Yayasan Perguruan Cikini, Jakarta. Akan tetapi, sejak tahun 1993, YPPSB menjejakkan kaki sendiri sehingga mendapatkan akreditasi dari Depdikbud Provinsi Kalimantan Timur dengan status “Disamakan” untuk unit SD dan SMP pada tahun 1994.
Pada awal berdiri, tahun 1991, YPPSB hanya memiliki satu gedung saja, yaitu bangunan SD YPPSB 1 (yang sekarang). Gedung tersebut diperuntukkan untuk tiga unit sekaligus, yaitu unit TK, SD, dan SMP. Satu tahun berikutnya, pada tahun 1992, PT Kaltim Prima Coal membangun gedung unit TK, sedangkan unit SMP dibangun pada tahun 1994.
Sejalan dengan tuntutan perkembangan jumlah murid yang terus bertambah, YPPSB melakukan pemekaran unit Sekolah Dasar pada tahun 2002. Pada tahun tersebut SD YPPSB dimekarkan menjadi dua unit yaitu SD YPPSB 1 dan SD YPPSB 2. Lima tahun berikutnya, tepatnya pada tahun 2007, YPPSB membangun gedung baru yang diperuntukkan untuk SD YPPSB 3, yang berlokasi di kawasan Perumahan Griya Prima Lestari (GPL) Munthe, Teluk Lingga, Sangatta Utara. Peresmian gedung SD YPPSB-3 dilakukan oleh Bupati Kutai Timur Bapak Awang Farouk Ishak, M.Si.
Sebagai bentuk pelayanan pendidikan yang berkelanjutan, tepatnya pada tahun pembelajaran 2023/2024 YPPSB menambah satuan pendidikan baru SMA Prima dengan konsep Ketarunaan dan Bilingual. Angkatan perdana terdiri 4 rombongan belajar (141 peserta didik), dan Kepala sekolah bapak Syafi’i, M.Pd. Berdirinya SMA Prima ini semakin menguatkan visi YPPSB sebagai lembaga pendidikan dengan lulusan yang unggul dan berkarakter.