Masyarakat Orang Asli di Bekok tinggal di Kampung Selai, Kampung Kemidak, Kampung Kudong, Kampung Tamok dan Kampung Sri Tembayan. Hasrat mereka untuk menghantar anak ke sekolah tidak terlaksana kerana kedudukan tempat tinggal mereka yang jauh dari Pekan Bekok khususnya di SK Seri Bekok.
Tok Batin Yem (Batin Kampung Kudong) ketika itu bersama penduduk tempatan cuba meminta pertolongan daripada pihak kontraktor pembalakan bagi membina sebuah bangunan separuh kekal untuk dijadikan sebuah sekolah. Akhirnya impian tersebut terhasil dengan persetujuan pihak kontraktor memberi ‘sumbangan’ kepada masyarakat Orang Asli setelah mereka menerokai kawasan pembalakan di kawasan tersebut.
Hasil sumbangan itu terbinalah sebuah bangunan yang mempunyai 3 buah bilik (2 bilik kelas dan sebuah pejabat) beserta kemudahan tandas pada tahun 1985. Oleh kerana tiada bekalan elektrik dan air, sungai dijadikan sumber air. Sekolah ini diwujudkan di bawah pentadbiran SK Seri Bekok. Hanya 3 orang guru dari SK Seri Bekok ditempatkan mengajar di sekolah ini antara tahun 1985-1992. Bilangan muridnya tidak sampai 20 orang.
Kampung ini mendapat namanya dari sebuah sungai. Menurut Tok Batin, asal Kampung Kudong ini ialah Sungai Kudong. Penempatan Orang Asli ini adalah berhampiran dengan sungai bagi memudahkan memperolehi sumber ekonominya. Hasil proses geologi, akhirnya aliran sungai asal terputus/terkudung menyebabkan masyarakat Orang Asli berpindah ke kawasan lain.
Tok Batin telah membuka penempatan baru dan dinamakan Kampung Kudong sempena sungai yang kudung itu. Maka pembinaan sekolah tersebut juga akhirnya dinamakan SK Kampung Kudong. Peninggalan sungai yang kudung tersebut ada sehingga hari ini.
Sekolah ini terletak 12 kilometer dari Pekan Bekok dan 68 kilometer dari PPD Segamat. Perhubungan melalui jalan darat yang telah berturap hingga ke Kampung Tamok. Walaupun begitu kerja-kerja pembalakan masih lagi berjalan dan ini menyebabkan permukaan jalan tidak rata dan berlubang-lubang.
Sekolah ini ialah sebuah sekolah yang muridnya terdiri daripada 100% anak-anak Orang Asli daripada Suku Jakun. Majoritinya bukan beragama Islam. Pertambahan murid yang ingin bersekolah mendorong pembinaan bangunan baru bagi memberi keselesaan pembelajaran kepada murid pada tahun 1993. Bangunan tersebut mempunyai 3 buah bilik dan sebuah bilik perpustakaan. Pada tahun ini juga sekolah ini dijadikan sekolah yang mempunyai pentadbiran sendiri. Pada masa ini sekolah mempunyai murid seramai 50 orang dan 5 orang guru di bawah pentadbiran Guru Besar yang pertama iaitu Tuan Haji Jumaat bin Diman
Pada 26.9.95, En. Katigo bin Sukiman telah mengambil alih tugas sebagai Guru Besar di sekolah ini bagi menggantikan Tuan Haji Jumaat yang bertukar ke SK Palong Timur 1. Pertambahan murid memaksa tambahan 2 bilik darjah lagi dibina bersambung dengan banguan asal bagi melengkapkan kemudahan bilik darjah pada tahun 1996.
Pada 1.7.00, Guru Besar sekolah ini diambil alih oleh En. Musa bin Salan menggantikan En. Katigo yang berpindah ke SK Seri Bekok.. Sebuah stor bagi menempatkan ruang bilik operasi SPBT dan stor sukan telah dibina pada November 2000. Mulai 1.3.03 hingga sekarang, En. Azali bin Othman telah mangambil alih tugas sebagai Guru Besar SK Kampung Kudong menggantikan En. Musa b Salan yang berpindah ke SK Bandar Renggam.
Di sekolah ini juga pada tahun 1985 mempunyai sebuah asrama yang dibina oleh pihak Jabatan Hal Ehwal Orang Asli (JHEOA) bagi menempatkan murid yang tinggal jauh terutama dari Kampung Selai, Kampung Kemidak dan Kampung Tamok. Semua pentadbiran asrama pada ketika itu di bawah tanggungjawab JHEOA. Mulai Jun 1996, Pihak Kementerian Pendidikan Malaysia telah mengambil alih perntadbiran asrama ini. Mulai saat ini asrama ini telah berubah wajah. Segala kelengkapannya dan peruntukan membaik pulih telah dilaksanakan oleh pihak Kementerian Pendidikan Malaysia.
Bagi menarik minat Orang Asli agar kehadirannya mantap, pelbagai program disusun dan dirancang oleh pihak sekolah sepanjang tahun 2001. Program ini mendapat sokongan dan bantuan daripada pelbagai agensi kerajaan dan badan berkanun. Program ini telah memberi impak terhadap kehadiran murid bahkan dari segi pertambahan murid untuk datang ke sekolah.
Namun murid-murid serta guru-guru terpaksa meninggalkan bangunan sedia ada untuk berpindah ke sekolah sementara yang terletak kira-kira 300 meter dari bangunan asal kerana bangunan asal sedang dalam pembinaan semula. Bangunan sementara merupakan 8 buah kabin yang dibina di satu kawasan lapang. Manakala asrama pelajar pula dipindahkan ke bangunan Jabatan Hal Ehwal orang Asli. Bangunan sementara ini terletak di kawasan lapang berdekatan dengan Dewan kampung Kudong. Namun, semua itu tidak menghalang guru-guru dan murid-murid untuk terus ke sekolah dan menjalankan tanggungjawab masing-masing.
Pada 25 Februari 2010, jawatan Guru Besar sekolah ini telah digantikan oleh Puan Rosnah bte Yaakob. En Azali bin Othman yang merupakan guru besar sebelum ini telah dilantik menjadi Penyelia Kanan Sukan di PPD Segamat.
