La chiesa ha origini molto antiche. Attorno alla basilica di Santa Maria Maggiore sorsero molte chiese, tra cui, come attesta una lapide del 491, un titulus Praxedis. Questo fa riferimento alle vicende della famiglia del senatore Pudente (I secolo d.C.), che la tradizione enuclea tra le prime persone convertite a Roma dall'apostolo Paolo; con Pudente si convertirono al cristianesimo anche le figlie Pudenziana e Prassede.

Pudente possedeva una villa i cui resti sono nove metri sotto l'attuale basilica, nella quale nascondeva i cristiani perseguitati, secondo alcune fonti anche l'apostolo Pietro. Quando Pudente subì il martirio sotto Nerone, Prassede e Pudenziana, con il consenso del Papa Pio I fecero costruire nel 142/145 c.a un battistero per battezzare i i nuovi cristiani. Anche Prassede e Pudenziana subirono il martirio durante le persecuzioni di Antonino Pio.

La pianta della Basilica, prende come modello la pianta della primitiva Basilica di San Pietro, con una navata centrale, due navate laterali divise da colonne, un transetto e un'abside, all'esterno un portale con scalinata e un portico. La basilica è a tre navate suddivisa da colonne e dai pilastri che reggono gli arconi di rafforzamento del XIII secolo.