The Catholic Church arrived in the Kingdom of Kongo shortly after the first Portuguese explorers reached its shores in 1483. The Portuguese left several of their own number and kidnapped a group of Kongo including at least one nobleman, Kala ka Mfusu, taking them to Portugal where they stayed a year, learned Portuguese and were converted to Christianity. The group was returned to Kongo in 1485 and Kala ka Mfusu led a royal mission from Kongo's manikongo, Nzinga a Nkuwu to Portugal. Following their arrival in late 1486 the embassy stayed nearly four years in Lisbon with the monks of Saint John the Baptist. There they studied Christianity and Portuguese with Vicente dos Anjos (who also learned to speak Kikongo), and began the start of a Kongolese version of Christianity.

The mission returned to Kongo in early 1491, although Kala ka Mfusu died on the return trip. The provincial ruler of Soyo on the Atlantic coast received them and was the first to be baptized. They moved to the royal capital in April and May and Manikongo Nzinga a Nkuwu was baptized on 3 May 1491, taking the name João in honor of the Portuguese king, (João II). Many of his officials and nobles were subsequently baptized. While initially reluctant to allow the baptism of women, his wife, Nzinga a Nlaza, protested and eventually won him over; she was subsequently baptized as Queen Leonor of Kongo and became a champion of the church, paying expenses from her own income.

Further missionaries arrived at the court of Nzinga a Nkuwu, beginning in 1508 and a good number also accompanied his son Afonso Mvemba a Nzinga to his provincial post of Nsundi. Afonso, in turn became a great champion of the faith, even though, according to Afonso's subsequent account of the events, his father cooled in the faith and many of the Kongolese who had been baptized turned away.

Afonso, whose letters are largely the sole source for the following events of his reign, presented himself to the world as a fervent Catholic, anxious to spread the faith, and also as having suffered persecution for it during the last years of his father's reign. When João died, probably in late 1506 or 1507, Afonso's half brother Mpanzu a Kitima, one of the lapsed Christians and a powerful rival, challenged the prince for the throne. But Afonso was able to overcome his brother in battle, thanks to having already positioned himself in the capital São Salvador and, according to Afonso's account the supernatural appearance of Saint James the Great in the sky, frightening his enemies. In subsequent correspondence with Portugal, Afonso decided to create a coat of arms in which five armed hands, each bearing a sword, was the principal element, along with a broken idol figured prominently. This coat of arms, first described in 1512, became one of Kongo's central icons, while Saint James Major's feast day became Kongo most important holiday, simultaneously honoring the saint who was popular in Iberian armies as a crusading saint, and King Afonso and his miracle.

Having become king, Afonso set about establishing a church. In letters to Portugal, he described some of the steps: he declared it illegal for people to worship idols, he destroyed a "house of idols" located in the capital (against the threat of a revolt), he also provided for a tithe to support it financially. Tradition from the late 17th century onward regarded Afonso as the founder of the church, and also attributes the story that he buried his own mother alive "for the sake of the Savior King" when she refused to take off a small idol she wore around her neck. Afonso's work to establish the church won him wide praise outside of Africa, and the Portuguese historian João de Barros called him the "Apostle of Congo" in 1552.

Afonso also worked to create a specifically local interpretation of Christianity, although the details are not well known. He worked with a number of Portuguese priests, most notably Rui d'Aguiar who came in 1516, and also with Kongolese who were educated in Europe, principally his son Henrique Kinu a Mvemba, who was elevated to the status of bishop in 1518, and who worked in Kongo from 1521 until his death in 1531.

The Church that Afonso created was not simply a copy or extension of the Portuguese church, but from the very beginning included elements of Kongo theology. For example, the Kongos probably believed that most of the denizens of the Other World were the souls of deceased ancestors, and not gods who had never lived on earth or had a material existence. Thus, the catechism described the Holy Trinity as "three people" (antu a tatu). Priests were called by the same name as the previous clergy (nganga), and the term ukisi, an abstract noun from the same root that gives the word nkisi (typically used to describe a charm, or in 16th century parlance, an "idol") was used to translate holy.

In fact, key religious terms such as God, holy, and spirit were rendered in Kikongo terms taken directly from Kongo cosmology (Nzambi Mpungu for God, nkisi for holy and moyo for spirit or soul). This in turn, made conversion easier, as self-identification requires only a simple declaration of faith.