Towarzysze Karola Lwangi

Za czasów króla Suna, w stronach Kalemba. osiedlili się Arabowie wyznający islam - Maciej nawiązał z nimi kontakt, a następnie przyjął islam, ponieważ te wierzenia wydawały mu się lepsze niż przesądy. Najprawdopodobniej to właśnie wtedy wstąpił na służbę do Muktivenda, naczelnika prowincji Singo. W Mitiyana, gdzie rezydował, poznał Noego Mwaggali, garncarza Mukwenda. Szybko zostali przyjaciółmi i Kalemba przyczynił się do tego, że Mwaggali również przyjął islam. Muzułmanie cieszyli się wtedy uprzywilejowaną pozycją. Sam Mutesa i wiele setek członków plemienia Baganda zostało muzułmanami.

Jednakże pod koniec 1874 roku, albo na początku 1875, król zezłościł się, ponieważ wielu młodych ludzi, służących na jego dworze, nie chciało jeść podanego mięsa, gdy zwierzę nie zostało zabite według rytuału muzułmańskiego. Mutesa dał im odczuć swój gniew i rozkazał zabić wszystkich, którzy byli obrzezani. Kalemba powie później: „Udało mi się zataić moje nawrócenie i nadal uchodziłem za przyjaciela naszych bożków, ale w ukryciu zawsze pozostawałem wierny praktykom islamu".

Młody Kalemba ciągle poszukiwał Boga w swym sercu. Był inteligentny i odznaczał się rozsądkiem. Był ponadto niezwykle energiczny, czasami okazywał swą dumę, a nawet dawał odczuć siłę. Mukwenda bardzo cenił sobie Kalembę ze względu na jego odwagę; mianował go jednym z przełożonych, nadał mu imię Mulumba (Śmiały) i polecił mu rozstrzygać wszystkie procesy, które miały miejsce w tej prowincji.

Właśnie wtedy sławny podróżnik Stanley przybył do królestwa Buganda i zdobył zaufanie Mutesa i jego dworu. W lipcu 1877 roku przybyli pierwsi misjonarze protestanccy. Mulumba i inni członkowie z plemienia Baganda zaczęli słuchać Pisma św. i komentarzy misjonarzy.

Kiedy przybyli misjonarze katoliccy, Mackay, jeden z protestantów, ostrzegł go i poradził mu unikanie wszelkich kontaktów z nimi, ponieważ nie znają prawdy i czczą Maryję. Dlatego też, kiedy Mukwenda polecił mu nadzorowanie budowy jednego z domów misjonarzy, trzymał się na dystans, ale zachowanie misjonarzy intrygowało go i postanowił uczestniczyć w ich lekcjach. Dołączył do niego jego przyjaciel Banabakintu, a nieco później Mawaggali. Mulumba, od momentu nawrócenia, usiłował ze wszystkich sił zapanować nad swą dumą i opanować impulsywny temperament. Był poligamistą, ale, zanim przyjął chrzest, oddalił - poza jedną - wszystkie żony, dając w ten sposób dowód swej głębokiej wiary. O. Livinhac przed udzieleniem mu chrztu powiedział:

- Jeśli myślisz powrócić do protestantyzmu, to będzie lepiej, żebyś nie przyjmował chrztu.
- Nie bój się, ojcze, już od dwóch lat jestem zdecydowany i nikt nie będzie mógł odwieść mnie od podjętej decyzji. Jestem katolikiem i umrę jako katolik.
Przyjął chrzest 28 maja 1882 roku, w dzień Zesłania Ducha św., razem z Łukaszem Banabakintu, Janem Chrzcicielem Tagwista i Cyprianem Kamya.