Le origini di questa chiesa sono antichissime e risalgono all'VIII secolo, come si ricava da diversi passi del Liber Pontificalis e da resti portati alla luce dal de Waal alla fine dell'Ottocento (antiche pitture risalenti al IX secolo, ed altre del XIII-XIV secolo). Alla chiesa era annesso un ospedale per pellegrini ed un cimitero.
Costruita sui resti della Naumachia citata nei Cataloghi regionari come esistente nell'Ager Vaticanus (forse quella inaugurata nel 109 da Traiano) la chiesa fu detta inizialmente "San Pellegrino in Naumachia" e (forse perché) dotata da Carlo Magno nell'800, in occasione della incoronazione in S. Pietro, di reliquie di un san Pellegrino martire in Auxerre.
Fabrizio Mancinelli, "La chiesa di San Pellegrino in Vaticano e il suo restauro", in: Bollettino monumenti musei e gallerie pontificie 3 (1982), pp. 43–62; Roma: Tipografia Poliglotta Vaticana
Claudio Rendina, Le Chiese di Roma, Roma, Newton & Compton Editori, 2000, p. 290, ISBN978-88-541-1833-1.