The first Protestant missionaries who tried to reach the Batak highlands of inner Northern Sumatra were English and American Baptist preachers in the 1820s and 30s, but without any success. After Franz Wilhelm Junghuhn and Herman Neubronner van der Tuuk did intensive research on Batak language and culture in the 1840s, a new attempt was done in 1861 by several missionaries sent out by the German Rhenish Missionary Society. The first Bataks were baptized in this year. In 1864, Ludwig Ingwer Nommensen from Rhenish Missionary Society Germany, reached the Batak region and founded a village called "Huta Dame" in the district of Tapanuli in Tarutung, North Sumatra. The RMG was associated with the Unierte Kirche, or union of Lutheran and Reformed churches. However, Nommensen and local leaders developed an approach that applied local custom to Christian belief. Already in 1868, a local seminary for the education of teachers was opened in Sipirok, and in 1877 a seminary for the education of preachers was built in Pansurnapitu. 1881, Nommensen was officially nominated "ephorus" of the Batak congregations by the RMG. In 1885, the first Batak ministers were ordained in Pearaja Tarutung, where the HKBP headquarters is located until this day. In 1889, the RMG sent out Sr. Hester Needham who started the work with girls and women and later established the first Batak deaconesses. In the last quarter of the 19th century, further missionaries of the RMG were sent out to the other Batak tribes. , North Sumatra, built circa 1917. In 1917, the "Hatopan Christen Batak" which later became one of the nucleus for the independent Batak church, was founded in Tapanuli as a social movement. In 1922, the first General Synod of all Batak congregations was held In 1931 HKBP became the first independent self-governing Christian body in what was then the Dutch East Indies. In 1940, all Germans working for the RMG, including pastors and ministers, were detained by the Dutch government. Rev. Sirait was chosen by the synod the first indigenous ephorus of HKBP. In 1952, while maintaining its indigenous character, the HKBP became a member of the Lutheran World Federation. In 1954, HKBP founded Nommensen University. In 1977, Sekolah Tinggi Theologia HKBP split from Nommensen University. Over the years, a number of church bodies have split from HKBP for various cultural and doctrinal reasons. However, HKBP remains the largest Indonesian LWF member by a factor of ten and also remains in communion with daughter church bodies through the LWF. Tarutung and the Batak region remain the stronghold for the HKBP in the predominantly Muslim nation of Indonesia, although worshippers are found throughout Indonesia and the United States. Well known HKBP congregants include Amir Sjarifuddin, Todung Sutan Gunung Mulia, and General Tahi Bonar Simatupang. In January 2010 two churches were burnt down in Sibuhuan.
The book of liturgical procedure used by the HKBP is referred to as the "Agenda" or formerly as the "Agende". This term comes from the European Protestant use of agenda.
