L'església, en la seva forma actual, va ser un encàrrec del papa Adrià I al voltant del 780 i es va construir a sobre de les restes d'una estructura del segle v. Va ser dissenyada per a guardar les relíquies de les santes Pràxedes i Pudenciana, les filles de sant Prudenci, tradicionalment el primer convers cristià de Pau de Tars a Roma. Les dues santes van ser assassinades per proporcionar un enterrament cristià als primers màrtirs desafiant la llei romana.[cal citació]

La basílica va ser ampliada i decorada pel papa Pasqual I al voltant del 822. Aquest papa, que va regnar entre 817 i 824, seguint l'ideari de Carlemany, tenia la intenció de tornar als fonaments del Cristianisme teològicament i artística. Per això va iniciar la recuperació d'ossos de màrtirs de Roma i la construcció de diverses esglésies. En aquesta església es guarden moltes relíquies per aquest motiu. Els mosaics de l'església són de gran valor.[1]