La iglesia fue construida en el siglo IX por decisión del papa Paulo I, sobre un preexistente oratorio.

Tras la restauración realizada en el siglo X, recibió la dedicación a la Virgen y el nombre de Santa Maria Nova para distinguirla de la otra iglesia del Foro que estaba también dedicada a María (Santa Maria Antiqua), y que había quedado destruida por un terremoto en el siglo IX.

En el siglo XII el edificio fue sometido a una importante reestructuración con el añadido de un campanario y la decoración del ábside.

En la actualidad la basílica se encuentra bajo la administración de los monjes benedictinos olivetanos.

El lugar donde se encuentra la iglesia, era, según la tradición, el de la muerte de Simón el Mago, quien, según la leyenda quiso demostrar tener más poder que san Pedro y san Pablo y se puso a levitar delante de ellos.