La prédication de Paul et des autres disciples du Christ entraîne la multiplication de petites communautés de croyants. On les appelle Églises, du grec ekklésia, assemblée.
La plus importante de ces communautés est celle de Jérusalem. Elle est dans les premiers temps animée par d'anciens compagnons du Christ : Simon, dit Pierre, et Jacques dit le Juste. Cette communauté se montre attachée à la Loi hébraïque et aux rituels juifs. Ses membres fréquentent assidûment le Temple.
En l'an 48 se tient à Jérusalem ce qu’on appelle le premier concile, ou concile des Apôtres. Venus de différents endroits de l'empire romain, les participants s'inquiètent d'être confondus avec l'une des nombreuses sectes messianiques caractéristiques du judaïsme. Alors, Paul plaide l'abandon des rituels juifs, en particulier de la circoncision, au nom de l'universalité du message de Jésus.
À la différence des juifs qui admettaient qu’on se convertisse à leur foi mais exigeaient que les nouveaux juifs commencent par se faire circoncire, les chrétiens rejettent la circoncision et les interdits alimentaires, nombreux chez les juifs, puisqu’ils ont été désapprouvés par Jésus-Christ. Ils n’acceptent que le sacrement de baptême par l'eau comme rite d'entrée dans leur religion. C'est ainsi que les chrétiens fondent une religion véritablement nouvelle et ouverte à tous les hommes. 

Paul, un révolutionnaire
Paul est appelé l'Apôtre des Gentils, c'est à dire des non-juifs. Ses quatorze lettres ou épîtres diffusent un message autant révolutionnaire que religieux en proclamant l'égalité de tous les êtres humains, indépendamment de leur sexe, de leur race, ou de leur statut social. Deux mille ans après, le message de Paul garde sa force subversive. Les épîtres de Paul sont ajoutées aux quatre Évangiles qui racontent chacun à leur manière la prédication de Jésus. L'ensemble de ces textes constitue la base doctrinale de la nouvelle religion, sous le nom de Nouveau Testament, par opposition à la Bible judaïque qui constitue l'Ancien Testament.

Du fait de l'importance de son message, Paul est souvent considéré comme le deuxième pilier du christianisme avec saint Pierre.  Il est mort à Rome, comme Pierre, lors des persécutions ordonnées par l'empereur Néron. De là vient la place particulière qu'occupe Rome et son évêque, le pape, dans l'Église. D'ailleurs, dans les premiers siècles de notre ère, les papes n'ont eu de cesse de se présenter comme les «successeurs de Pierre et Paul» (les papes modernes ne font plus référence qu'au premier).