Otra tradición afirma que se construyó durante el reinado de Ezana, el primer gobernante cristiano del Reino de Axum (actual Eritrea y Etiopía), durante el siglo IV.
[1] Desde su fundación durante el obispado de San Frumencio, la iglesia ha sido destruida y reconstruida al menos dos veces.
La primera destrucción ocurrió a manos de la reina Gudit en el siglo X.
La segunda, fue en el siglo XVI, por obra de Ahmad ibn Ibrihim al-Ghazi, tras lo cual fue reconstruida por el emperador Gelawdewos, y luego ampliada por Fasilides en el siglo XVII.
[4][5][6] En los años 1950, el emperador Haile Selassie construyó una nueva catedral, abierta a hombres y mujeres, próxima a la antigua, que permanece abierta solo para los hombres.