The article uncovers how the first five centuries of Greek Christian texts reflect a changing understanding of Paul as a prototypical character. The study joins cognitive and social psychological theory of categorization in defining prototype as a highly contextual, fuzzy set of qualities which captures the make-up of the ingroup in comparison to outgroups. Paul as a prototypical character thus illustrates a group-level logic and an attempt at group identity construction by the early Christian authors. Textual source material poses special challenges because, strictly speaking, prototypes exist only in human cognition and because ancient texts do not accurately represent the social reality behind them. The study approaches prototypical depictions of Paul with the help of distributional semantics models that consider language as, likewise, highly context-dependent and, importantly, allow access to a deeper “meaning” of Paul on a cognitive level beyond mere co-occurrence of words in a given text. The analysis shows that while Paul is in the first three centuries linked, among other things, to oral tradition, gentile mission, and Judaism, the 4–5th centuries connect him to church offices, anti-heretical struggle, and doctrinal content. Curiously, in the later period, Paul also becomes distanced from the figure of Jesus/Christ, perhaps because the latter became veiled in high Christological dogma.