Naiborhu merupakan salah satu marga yang dibawa oleh keturunan Raja Bungabunga atau Raja Parmahan Silalahi, keturunan dari Silahisabungan. Dengan kata lain, marga Naiborhu merupakan salah satu marga yang merupakan keturunan dari Silahisabungan.
Adapun Raja Silahisabungan menikah dengan Pinggan Matio Boru Padang Batanghari dan Similing-iling (Nailing) Boru Narasaon dan menetap di Silalahi Nabolak. Raja Silahisabungan kemudian memiliki delapan orang putra dan seorang putri yang bernama Deang Namora. Adapun kedelapan putra tersebut antara lain adalah:
Marga Naiborhu sendiri berasal dari Sondi Raja yang mana Sondi Raja menikah dengan Siboru Nagok Boru Siboro dan memiliki dua orang putra, yaitu Rumasondi dan Rumasingap. Kemudian Rumasondi menikah dengan Boru Siboro dan memiliki dua orang putra, yaitu Bolon Raja dan Raja Bungabunga yang kemudian dikenal juga sebagai Raja Parmahan Silalahi.
Raja Bungabunga/Raja Parmahan Silalahi kemudian diculik oleh Tuan Sihubil dan dibawa ke Balige, lalu kemudian di sana ia mengadakan perjanjian dengan Tuan Sihubil dan diangkat menjadi anak angkat dari Tuan Sihubil. Raja Bungabunga/Raja Parmahan Silalahi kemudian menikah dengan Antar Mangatur Boru Pasaribu dan menetap di Balige. Kemudian ia memperoleh empat orang putra yang mana nama dari keempat putranya tersebut terinspirasi dari nama-nama keturunan Silahisabungan yang merupakan generasi di atas Raja Parmahan. Adapun nama dari keempat putra tersebut di antaranya adalah (1) Sinaloho, (2) Sinagiro, (3) Sinabang, dan (4) Sinabutar. Raja Bungabunga/Raja Parmahan juga memiliki seorang putri yang bernama Tiurma Uli yang dinikahi oleh marga Panjaitan.
Adapun Sinagiro kemudian menikahi Pintaomas Boru Siregar dan memiliki dua orang putra, yaitu Sangga Raja dan Ompu Runggu. Kemudian Ompu Runggu memiliki empat orang putra yaitu (1) Tuan Sada, (2) Tuan Sampur, (3) Tuan Nahoda, dan (4) Raja Pangindingan Silalahi yang menjadi leluhur dari marga Naiborhu.
Raja Pangindingan Silalahi Naiborhu yang bergelar Raja Huta Borhu atau Raja Naiborhu yang kemudian membawa marga Naiborhu menikah dengan Boru Pasaribu dan menetap di Balige. Kemudian ia memperoleh seorang putra yang bernama Tuan Bungkung, dan Tuan Bungkung sendiri menikah dengan Boru Sitorus Pane dan menetap di Lumban Borhu Nagatimbul, Toba. Di sana kemudian ia memperoleh ketiga orang putranya, yaitu antara lain (1) Ompu Jongok, (2) Raja Hutabatu, dan (3) Raja Mallengat.
Ompu Jongok kemudian tetap bermukim di Lumban Borhu Nagatimbul dan di sana ia memperoleh seorang putra yang bernama Partungkot Bosi. Adapun Partungkot Bosi kemudian menikahi Boru Sitorus dan memperoleh empat orang putra, yaitu (1) Namora Sungkunon yang menikahi Boru Lubis, (2) Raja Halissung yang menikahi Boru Manurung, (3) Namora Sotaralo yang kemudian menikahi Boru Sitorus, dan (4) Tuan Ri yang kemudian menikahi Boru Hutajulu.
Raja Hutabatu menetap di Sitorang dan kemudian ia menikah dengan Boru Panjaitan serta memperoleh tiga orang putra, yaitu (1) Mangasa Pintor, (2) Sabungan Mangolat, dan (3) Raja Margumis. Mangasa Pintor sendiri menetap di Naiborhu Dolok, Natolu Tali Sitorang. Kemudian Sabungan Mangolat yang menikah dengan Boru Silaen menetap di Naiborhu Toruan, Natolu Tali Sitorang memiliki dua orang putra, yaitu Saribu Raja yang menikah dengan pariban nya Boru Silaen dan Patutanggang. Adapun anak bungsu dari Saribu Raja yang bernama Lobe Dugar merantau ke Tanjung Balai. Lalu Raja Margumis yang menikah dengan Boru Hutagaol serta menetap di Naiborhu Toruan juga dan memperoleh dua orang putra, yaitu Raja Partolu yang menikah dengan Boru Parhusip dari daerah Nainggolan serta Boru Lumbantungkup dari daerah Nainggolan dan Ompu Diha yang menikahi Boru Pasaribu serta pergi ke Parsoburan.
Raja Mallengat menikah dengan Boru Sirait dan menetap di Lumban Borhu Nagatimbul kemudian belia menikah dengan Boru Sirait serta memperoleh dua orang putra, yaitu Negeri Singkam yang menikahi Boru Sirait dan Puntarugun yang menikah dengan Boru Butarbutar serta menetap di Parsingguran Sitorang.