He studied philosophy (1937–40) and theology (1940–44) at the Major Seminary of Christ-Roi in Kabwe. He served as a professor at the Minor Seminary of Bokoro from 1944 to 1946 as well. Malula was ordained to the priesthood by Bishop Georges Six, CICM, on 9 June 1946, in the Stade Reine Astrid. He then resumed teaching at the minor seminary, and served as vicar and pastor at several parishes in Léopoldville. In 1953, he visited Algiers, Tunisia, Malta, Rome, and Belgium.
Pope Paul VI created him Cardinal Priest of Santi Protomartiri a Via Aurelia Antica in the consistory of 28 April 1969. He was the first cardinal from Zaire. At a Mass in 1970, at which President Mobutu was present, the Cardinal claimed Zaire's ruling class was enriching itself and ignoring the people's misery[1] In 1971, despite being an advocate of African culture, he expressed his disapproval of Christians giving up their baptismal names in an article in the Catholic weekly magazine, Afrique Chrétienne, following the renaming of the Republic of the Congo as the Republic of Zaire.[2] President Mobutu subsequently removed the Cardinal from his government-owned residence and suspended the magazine for six months. Malula was one of the cardinal electors who participated in the conclaves of August and October 1978, which selected Popes John Paul I and John Paul II, respectively. He supported Albino Cardinal Luciani at the August conclave, and even gave him a public embrace before he was elected.[3]
Before the October conclave began, he spoke of the Vatican's pomp, saying, "All that imperial paraphernalia. All that isolation of the Pope. All that medieval remoteness and inheritance that makes Europeans think that the Church is only Western. All that tightness that makes them fail to understand that young countries like mine want something different. They want simplicity. They want Jesus Christ. All that, all that must change."[4]