Tymczasem w okolicach połowy VI wieku cesarz Justynian, będący zdania, iż tylko chrystianizacja plemion nubijskich przyniesie spokój egipskiej granicy imperium, zaczął wysyłać tu misjonarzy, którzy głosili oczywiście doktrynę, której przychylny był cesarz, czyli diofizytyzm.
W zależności od regionu chrystianizacja Nubii przebiegała różnie, choć wydaje się, że była raczej pokojowa. Zdarzało się jednak, że pozyskanie dla chrześcijaństwa lokalnych władców kończyło się prześladowaniami ich poddanych pozostających przy rodzimych kultach (nosząca ślady zniszczenia świątynia z Qasr IbrimThe Nubian Christian Kingdoms: 600-1500 AD.). Prawdopodobnie to właśnie owocem tego ruchu misyjnego było przyjęcie chrześcijaństwa przez władców Alodii w VI wieku, prawdopodobnie w 580 roku. Ciężko stwierdzić, na ile nowa religia obejmowała ogół mieszkańców, ale wydaje się, że z biegiem czasu skutecznie wyparła ona stare kulty. XIII-wieczny kronikarz koptyjski, Abu al-Makarim, pisał, że w królestwie Alwy istnieje aż czterysta kościołówAtiya, Aziz S., Historia kościołów wschodnich, s. 375..