Dans un espace ouvert sur l’extérieur comme l’est alors la province d’Afrique, le christianisme se développe de façon précoce grâce aux colons, commerçants et soldats, et la région devient l’un des foyers essentiels de la diffusion de la nouvelle foi, même si les affrontements religieux y sont violents avec les païens. Dès le IIe siècle, la province applique aussi les sanctions impériales, les premiers martyrs étant attestés dès le 17 juillet 180 : ceux qui refusent de se rallier au culte officiel peuvent être torturés, relégués sur des îles, décapités, livrés aux bêtes féroces, brûlés voire crucifiés. À la fin du IIe siècle, la nouvelle religion progresse dans la province car, malgré une situation difficile, la nouvelle foi s’implante plus vite qu’en Europe, notamment en raison du rôle social joué par l’Église d’Afrique, qui apparaît dans la seconde moitié du IIIe siècle, et du fait de la très forte densité urbaine. C’est à partir d’environ 400 que, sous l’action dynamique d’Augustin d'Hippone et l’impulsion de quelques évêques, les grands propriétaires terriens et l’aristocratie citadine se rallient au christianisme, où ils voient leur intérêt, l’Église intégrant alors les diverses couches sociales.

Rapidement, la province d’Afrique est considérée comme un phare du christianisme latin occidental. Cette expansion rencontre toutefois des obstacles, en particulier lors du schisme donatiste qui est condamné de façon définitive au concile de Carthage. Ce dernier accuse les schismatiques d’avoir coupé les liens entre l’Église catholique africaine et les Églises orientales originelles. En dépit de cette lutte religieuse, la conjoncture économique, sociale et culturelle est relativement favorable au moment du triomphe du christianisme, comme en témoignent les nombreux vestiges, notamment de basiliques à Carthage et de nombreuses églises aménagées dans d’anciens temples païens (comme à Sbeïtla) ou même certaines églises rurales découvertes récemment.

Le 19 octobre 439, après s’être rendus maîtres d’Hippone, les Vandales et les Alains entrent dans Carthage, où ils installent leur royaume pour près d’un siècle. Les Vandales sont adeptes de l’arianisme, déclarée hérésie chrétienne au concile de Nicée, ce qui ne facilite pas les relations entre eux et les notables locaux majoritairement catholiques. Or les Vandales exigent de la population une totale allégeance à leur pouvoir et à leur foi. En conséquence, dès lors qu’ils tentent de s’opposer aux Vandales, les chrétiens sont persécutés : de nombreux hommes d’Église sont martyrisés, emprisonnés ou exilés dans des camps au sud de Gafsa. Dans le domaine économique, les Vandales appliquent à l’Église la politique de confiscation dont doivent pâtir les grands propriétaires. Cependant, la culture latine reste largement préservée et le christianisme prospère tant qu’il ne s’oppose pas au souverain en place. Dans ce contexte, le territoire, enserré par des principautés berbères, est attaqué par les tribus de nomades chameliers : la défaite, en décembre 533 à la bataille de Tricaméron, confirme l’anéantissement de la puissance militaire vandale. Carthage est prise facilement par les Byzantins dirigés par le général Bélisaire, envoyé par Justinien, le roi vandale Gélimer se rendant en 534. Malgré la résistance des Berbères, les Byzantins rétablissent l’esclavage et instituent de lourds impôts. Par ailleurs, l’administration romaine est restaurée.

L’Église d’Afrique est mise au pas et Justinien fait alors de Carthage le siège de son diocèse d’Afrique. À la fin du VIe siècle, la région est placée sous l’autorité d’un exarque cumulant les pouvoirs civil et militaire, et disposant d’une large autonomie vis-à-vis de l’empereur. Prétendant imposer le christianisme d’État, les Byzantins pourchassent le paganisme, le judaïsme et les hérésies chrétiennes. Pourtant, à la suite de la crise monothéliste, les empereurs byzantins, opposés à l’Église locale, se détournent de la cité. Or, avec une Afrique byzantine entraînée dans le marasme, un état d’esprit insurrectionnel secoue des confédérations de tribus sédentarisées et constituées en principautés. Ces tribus berbères sont d’autant plus hostiles à l’Empire byzantin qu’elles ont conscience de leur propre force. Avant même sa prise par les Arabes en 698, la capitale et dans une certaine mesure la province d’Afrique se sont vidées de leurs habitants byzantins. Dès le début du VIIe siècle, l’archéologie témoigne en effet d’un repli.