Desa Karangbrai terbentuk  dari sekumpulan penduduk yang datang dari desa sekitar yaitu Desa Kesesi  Kabupaten Pekalongan, Desa Wonogiri Kecamatan Ampelgading, Desa Sukowati Kecamatan  Ampelgading dan lain lain.

Pada saat itu belum terbentuk pemerintahan desa yang pasti walaupun secara kewilayahan Karangbrai pada dasarnya sudah ada sejak pemerintahan Kesultanan Demak, Kesultanan Mataram, setelah ada utusan dari Kadipaten Pemalang dan Kadipaten Pekalongan dimusyawarahkan apakah wilayah Desa Karangbrai masuk dalam wilayah Kadipaten Pemalang atau Kadipaten Pekalongan.

Dalam pertemuan tersebut menghasilkan kesepakatan bahwa Desa Karangbrai masuk dalam wilayah Kadipaten Pemalang.

Namun  sebelum pemerintahan desa yang terorganisir tersebut terbentuk sesungguhnya Desa Karangbrai sudah ada pada zaman kerajaan majapahit dan padjajaran, dengan dibuktikan ada petilasan makam Sech Jambu Karang sekitar tahun 1250 M.

Menurut cerita tetua desa Karangbrai Sech Jambu Karang berasal dari kerajaan Padjajaran beliau adalah putra mahkota kerajaaan Padjajaran dengan gelar Adipati Mendang, Putra Prabu Barawijaya Mahesa Trandeman  I , Raja Padjajaran I dan nama kecilnya bernama Raden Mundingwangi karena beliau tidak berkenan menggantikan ayahandanya dan memilih menjadi Wiku/Pendeta beliau menyerahkan tahktanya kepada adiknya yang bernama Raden Mundingsari.

Raden Mundingwangi atau Adipati Mendang kemudian berganti nama dengan Jambu Karang, yang dalam perjalannan pengembaraannya setelah masuk agama Islam bergelar Sech jambu Karang, perjalannan pengembaraan  penyebaran agama Islam telah sampailah di suatu tempat, pada kala itu masih hutan belantara dan belum punya nama yang cikal bakalnya diberi nama Karangbrai yang artinya Karang yaitu tempat  dan brai asal kata dari blai berarti musibah apes istilah jawanya jalmo moro jalmo mati yaitu apabila ada manusia yang bermukim di tempat tersebut akan terkena musibah/apes dan bisa menemui ajal,  namun setelah didatangi oleh Sech Jambu Karang tempat tersebut lambat laun menjadi makmur dan aman jauh dari segala bahaya. Dalam legenda asal kata Karang juga berarti diambilkan dari kata belakang Sech Jambu Karang, yang merupakan tokoh penyebar  Agama Islam dikawasan Cirebon, Tegal, Pemalang, Pekalongan , Purbalingga yang merupakan Ulama Kharismatik Pribumi tanah Jawa sunda yang masuk agama Islam dari Keturunan luhur bangsawan seorang Penguasa / raja di tanah Sunda yang rela meninggalkan kemewahan, kedudukan sebagai seorang anak raja, dan rela mengabdikan diri untuk menyebarkan agama Islam dan  pertama  kali membuka pemukiman sekaligus memberi nama Desa Karangbrai.

Dalam perkembangannya Desa Karangbrai merupakan satu kawasan yang menjadi desa yang subur untuk tanaman pertanian sehingga warganya tidak kekurangan pangan tadinya merupakan hutan lebat yang konon kabarnya sangat tidak mungkin untuk didiami oleh penduduk pada akhirnya setelah Sech jambu Karang datang di Desa Karangbrai, satu persatu maka berdatangan para penduduk yang ingin menetap di Desa Karangbrai.

Bukti sejarah ada petilasan Sech Jambu Karang dan Sech Boga Jati di Desa Karangbrai yang masih terawat dan bukti alam yang masih melegenda adalah Kedung Sigolo-golo kali comal yang terletak antara perbatasan Kecamatan Ampelgading dan Karangbrai.

Dalam suatu riwayat beliau Sech. Jambu Karang melanjutkan perjalanan Syiar agama Islam ketempat lain dan kemudian secara organisasi pemerintahan yang berjalan secara sederhana dipimpin oleh seorang bekel atau lurah yang berkedudukan sebagai Abdi dalem pada zaman pemerintahan Kesultanan Demak beralih sesuai perkembangan pemerintahan, Kesultanan mataram, zaman penjajahan kolonialisme Belanda dan pada akhirnya setelah Indonesia Merdeka pada Tahun 1945 Desa Karangbrai secara otomatis masuk dan diakui dalam bingkai kesatuan NKRI.

Sampai pada saat pemerintahan dimana Lurah jabatan seumur hidup dipimpin oleh Lurah Wadmi tahun 1908-1922, dilanjutkan pada pemerintahan Lurah Rekso Sukaryo tahun 1922-1951, pada tahun 1951-1974 dipimin oleh Lurah Oesman b. Rekso sukaryo, pada tahun 1974 Oesman b. Rekso sukaryo wafat dan digantikan hasil pemilihan Kepala Desa tahun 1974 oleh Harsono 1974-1998.

Pada tahun 1998 diadakan pemilihan Kepala Desa dan terpilih H. Casmidi Al Kamalia 1999-2007. Kemudian diadakan pemilihan Kepala Desa dan Kepala Desa terpilih Casmirah Periode 2007-2012, tahun 2007 Casmirah terpilih kembali menjadi Kepala Desa yang Kedua Periode  2012-2018.