Según la tradición, la iglesia debe su nombre a Práxedes, hija del senador romano del siglo II Pudencio, discípulo de San Pablo. Ella y su hermana Santa Pudenciana fueron torturadas porque las sorprendieron protegiendo a cristianos y enterrando, en pozos cercanos, los cuerpos de los mártires durante las persecuciones de Antonino Pío. Santa Práxedes moriría más tarde no directamente por martirio, sino porque, horrorizada por el horror de las persecuciones, suplicó morir.
La iglesia original fue erigida a partir del siglo IX por el Papa Pascual I, y luego la estructura original fue remodelada hasta el siglo XIX, cuando alcanzó su aspecto actual.
En este lugar también se conmemora a los santos Cirilo y Metodio, patronos de todos los eslavos y traductores de la Biblia a la lengua eslava a instancias del Papa Nicolás I en 867. De hecho, vivieron en el monasterio de Santa Práxedes y, poco antes de su muerte, Cirilo, de acuerdo con su hermano, donó al Papa las reliquias del papa Clemente que habían llevado a Roma.