Η εκκλησία περιέχει ψηφιδωτό διάκοσμο, που την κάνει από τις παλαιότερες εκκλησίες της Ρώμης. Μία εκκλησία υπήρχε κοντά στο σημείο από τον 5ο αι., αλλά ο Πάπας Αδριανός Α΄ ανέθεσε περί το 780 να κτιστεί εκκλησία στη θέση και με τη μορφή που έχει σήμερα. Ήθελε να στεγάσει τα λείψανα της Αγ. Πρασέντε και της Αγ. Πουντεντσιάνα, κορών του Αγ. Προύντενς, πρώτου Ρωμαίου που έγινε χριστιανός από τον Άγ. Πέτρο. Το κτήριο κτίστηκε επάνω από τα κατάλοιπα αρχαιορωμαϊκών ιδιωτικών Θερμών του 4ου αι,, οι οποίες ανήκαν στην οικογένεια της Πουντετσιάνα και λεγόταν Θέρμες του Νοβάτο. Επειδή οι δύο αγίες έθαπταν τους πρώτους μάρτυρες, κατά παράβαση του ρωμαϊκού νόμου, σκοτώθηκαν. Περί το 822 η βασιλική διευρύνθηκε και διακοσμήθηκε από τον πάπα Πασχάλιο Α΄.

Ο ποντίφικας αυτός, που αρχιεράτευσε το διάστημα 817-824, ήταν πρωτοπόρος της Καρολίγγειας Αναγέννησης, την οποία ξεκίνησε και υποστήριξε ο Καρλομάγνος. Ήθελαν να επιστρέψουν στην ίδρυση του Χριστιανισμού θεολογικά και καλλιτεχνικά. Ο Πασχάλιος Α΄ λοιπόν ξεκίνησε δύο φιλόδοξα σχέδια: την ανακάλυψη των οστών των μαρτύρων από τις κατακόμβες της Ρώμης και μία άνευ προηγουμένου εκστρατεία ανοικοδόμησης. Ο πάπας ανέσκαψε πολλούς σκελετούς και τους μετέφερε στην εδώ εκκλησία. Ο καρδινάλιος, τιτουλάριος της Αγ. Πρασέντε, εγκαταστάθηκε π. το 112 από τον πάπα Ευάριστο.

Οι περιγραφές που βρέθηκαν στον ναό συλλέχθηκαν και εκδόθηκαν από τον Βιντσέντσο Φορτσέλα και είναι μία πολύτιμη πηγή, που δείχνει την ιστορία του ναού. Έγινε η έμπνευση για το ποίημα του Ρόμπερτ Μπράουνινγκ Ο επίσκοπος αναθέτει το ταφικό μνημείο του στον ναό της Αγ. Πασέντε. Η εκκλησία περιέχει το παρεκκλήσιο του Αγ. Ζήνωνος.