Asal nama Kampung Tebuk Berihun ini ialah berkaitan dengan kerja kerja menebuk (membuka) hutan yang dimulakan dari Kampung Simpang Empat hingga ke Tebuk Berihun. Semasa mula dibuka pada tahun 1916, kampung ini amat kurang penduduknya. Namun begitu, menjelang tahun 1925 anggaran penduduk pada masa itu adalah sekitar 220 keluarga. Sebelumnya, kawasan kampung ini merupakan hutan belantara yang amat tebal.
Menurut cerita, Kampung Tebuk Berihun telah diterokai dan dibuka oleh pendatang berketurunan Banjar dari Banjarmasin, Kalimantan bernama Haji Berihun iaitu pada tahun 1916. Beliau merupakan seorang pahlawan (panglima) yang handal dan berani. Beliau juga mempunyai kehebatan luar biasa dan mampu menebang hutan tidak kira siang atau pun malam. Haji Berihun telah dilantik menjadi ketua di kampung ini sejak mula dibuka sampailah menjadi sebuah kampung. Bermula dari tahun 1916, para peneroka mula menanam padi dan diikuti dengan tanaman kelapa.
Ada cerita menyatakan bahawa semasa mula-mula sampai ke kawasan ini, berlaku sedikit perbalahan di antara beliau dengan orang-orang Bugis yang juga membuka kawasan berhampiran. Pergaduhan ini berlaku pada tahun 1929. Pada mulanya, Haji Berihun tidak mengendahkan perselisihan yang berlaku. Namun begitu, lama kelamaan beliau agak hilang sabar lalu ditentangnya orang-orang Bugis tersebut. Beliau menyuruh kumpulan orang orang Bugis ini supaya mengumpulkan semua pahlawan mereka dan beliau akan berlawan cuma dua (2) beranak sahaja iaitu beliau dan anak saudaranya dan tidak perlu melibatkan ramai orang. Mengikut ceritanya, pergaduhan antara kedua belah pihak berlanjutan dari pagi hingga ke pukul enam petang. Ada yang mengatakan bahawa pertelingkahan ini berlangsung selama dua (2) minggu dan bekalan makanan sukar didapati pada ketika itu. Di akhir pertelingkahan, Haji Berihun meninggal dunia kerana kelaparan (tidak makan dan minum) walaupun kulitnya tidak terjejas oleh senjata. Begitu juga dengan anak saudaranya. Pada masa kini, kubur Haji Berihun dikatakan masih ada di suatu tempat bernama Tungkal, di Sumatera iaitu berhampiran dengan kubur anak saudaranya.
Dari segi pentadbiran kampung, Haji Berihun merupakan Ketua Kampung (Sidang) pertama di kampung ini. Setelah meninggal diunia, beliau digantikan oleh Sidang Haji Nasruni bin Saleh hingga tahun 1954. Selepas itu beliau diganti oleh anaknya Haji Durani (1958). Jawatan ini kemudiannya dipegang oleh Tuan Haji Sarkawi bin Haji Idris semenjak tahun 1958 hingga kini.Di Kampung Tebuk Berihun, terdapat kisah mengenai asal nama Sabak Bernam. Menurut cerita, terdapat enam (6) orang sahabat yang melarikan diri ke kawasan ini melalui sungai kerana berlakunya perbalahan di Kuala Selangor. Sampai di Sabak Bernam, kumpulan ini telah berpecah. Nama 'Sabak Bernam' itu dikatakan ada kaitan dengan sebutan orang Banjar kerana sahabat disebut 'Sabak' dalam bahasa Banjar. 'Berenam' pula maknanya enam (6) orang iaitu mengambil sempena jumlah sahabat tersebut.
