Sebelum berdiri SMA Negeri Sokaraja, di wilayah Kecamatan Sokaraja telah ada satu SMA, yakni SMA Pemda Sokaraja. SMA tersebut didirikan untuk memenuhi kebutuhan para siswa lulusan SMP di sekitar Sokaraja yang karena alasan tertentu tidak bisa melanjutkan sekolahnya di kota (Purwokerto). Untuk sementara SMA Pemda Sokaraja menempati Gedung SMP Negeri 2 Sokaraja yang terletak di desa Sokaraja Wetan, Kecamatan Sokaraja, Kabupaten Banyumas. Kegiatan  Belajar Mengajar pada saat itu dilaksanakan pada sore hari. Mengingat jumlah siswa SMA Pemda Sokaraja pada saat itu cukup banyak dan SMA tersebut tidak dapat menampungnya, maka timbul gagasan untuk mendirikan Gedung sekolah sendiri, agar nantinya pada siswa SMA Pemda Sokaraja bisa masuk  sekolah pada pagi hari. Untuk keperluan itulah, kemudian dibentuk Panitia Pendiri SMA Pemda Sokaraja.

      Langkah pertama yang dilakukan panitaia adalah mencari lahan untuk dijadikan lokasi pembangunan Gedung SMA Pemda Sokaraja. Masyarakat yang menyadari sepenuhnya bahwa keberadaan sebuah SMA di Sokaraja memang sangat dibutuhkan, maka warga/masyarakat setempat yang lahan/sawahnya mau dijadikan lokasi pembangunan Gedung SMA  Pemda Sokaraja.

     Beberapa saat setelah panitia berhasil memiliki lahan untuk loaksi pembangunan Gedung SMA Pemda Sokaraja, datanglah kiriman atau paket dana dari pemerintah pusat untuk membangun sebuah unit Gedung baru SMA di Sokaraja, melalui Daftar Isian Proyek Menteri Pendidikan dan Kebudayaan RI Nomor : 2224/0/1980, tanggal 11 Sepetember 1980. Dengan dana yang sepenuhnya berasal dari pemerintah pusat inilah kemudian di Sokaraja dibangun sebuah SMA di lokasi yang Sebagian telah menjadi milik Panitia Pendiri SMA Pemda Sokaraja, yang kemudian diberi nama SMA Negeri Sokaraja. Selanjutnya panitia pendiri SMA Pemda Sokaraja mendirikan Gedung sendiri dan kemudian mengubah nama SMA Pemda Sokaraja mendjadi SMA Budi Utomo Sokaraja.