Work among the Karo Batak people was started in 1890 by the Dutch Missionary Society, financially assisted by the Dutch Plantation Company. The Karo people used to accuse the missionaries of being agents of colonialism. The church grew slowly, at its 50th anniversary it had 5,000 members. The GBKP was founded at the first synod in 1941. At that time there were two ordained Karonese pastors. During the Japanese occupation the missionaries were detained in camps and the Karo Christians had to take responsibility, without proper preparation financially, institutionally, theologically or in terms of human resources. Two periods of rapid growth occurred in 1965 and 1966 with mass baptisms at the time of the repression of the communist rebellion, and in the 1980s through the family approach model of evangelization. The increase in numbers created a problem for the church because there were not enough pastors to teach the new members in the faith. To meet the need, elders and deacons were trained to conduct worship services and take over other tasks of the pastors. A lay training centre was set up and later a school for evangelists. Elders and deacons continue to fulfill important functions in the church, including pastoral responsibilities.

The GBKP is organized according to the presbyterian-synodal model. The general assembly is the highest governing body. In 2005 the general assembly voted a new church order. There are three departments: Diakonia (orphanages, care for the mentally handicapped, homes for the elderly, credit unions etc); Marturia (evangelization, Christian schools, theological education, pastoral counselling, etc.); Koinonia (Sunday schools, youth, women, lay training, retreat centre, etc.). For the next five years the programmes will put emphasis on theological and spiritual development, human resources development, and financial support. Some of the current challenges which the church faces are syncretism, formalism (“Sunday Christians”), materialism, drug abuse, HIV/AIDS, violence in the families, poverty and lack of skills in the rural areas, the belief that the church should not be involved in socio-economic and political issues, etc. Therefore the GBKP is giving high priority to programmes of education and training, lay participation, health, social and economic questions, a theology of giving (the tithe has been introduced), and continuous strengthening of all sectors and institutions of the church.

The GBKP would like to enter into partnership relationship with other churches, through the WCC, e.g. short-term exchanges South-North and South-South, twinning of congregations, mutual learning in mission, joint programmes of WCC member churches, etc.