Manoma, kad toje vietoje IX a. buvo krikščionių oratorija, skirta Mergelei Marijai. XI a. šioje vietoje pastatyta bažnytėlė, kuri pašventinta 1049 m. ir pavadinta „Naująja“. 1219 m. dokumentuoti 12 dominikonų vienuolių, kurie iš Bolonijos Šv. Dominyko pavedimu atvyko į Florenciją. Jiems įsikurti buvo skirta Santa Maria Novella bažnyčia. Ilgainiui už bažnyčios buvo pastatytas vienuolynas, o dėl didelio bažnyčios lankymo tapo reikalingas jos perstatymas. Lėšos perstatymui buvo pradėtos rinkti nuo 1248 m. Pagal vienuolių Fra Sisto Fiorentino ir Fra Ristoro da Campi projektą bažnyčia pradėta 1279 m. Prie bažnyčios statybos prisidėjusioms Florencijos kilmingoms šeimoms buvo skirtos atskiros koplyčios bazilikoje. 1287 m. Florencijos miesto valdžia patvirtino Santa Maria Novella aikštės projektą priešais bažnyčios fasadą. Bazilikos pastatas kartu su varpine baigtas apie 1360 m., tačiau vidiniai ir vienuolyno perstatymai užtruko. Bažnyčia pašventinta 1420 m. popiežiaus Eugenijaus IV-ojo. Tik fasado apatinė dalis, šoniniai pilioriai ir mažosios durys tuo metu buvo baigti. Senasis įėjimas į vienuolyną šiuo metu yra įėjimas į bazilikos muziejų.

1456 − 1470 m. laikotarpyje bazilikos fasadas buvo baigtas renesanso stiliumi pagal architekto Leon Battista Alberti projektus. Alberti į projektą įtraukė specialią ornamento juostą, kuri atskiria renesansinę ir gotikinę fasado dalis. Nuo 1567 m. pagal naujus Tridento susirinkimo reikalavimus bažnyčios vidus buvo perstatomas architekto Giorgio Vasari, po ko bažnyčia buvo papildyta manieristiniais elementais ir meno kūriniais, bei sukurtos dar 6 koplyčios.

Dž. Bokačo „Dekamerono“ veiksmas prasideda Naujojoje Švč. Marijos bazilikoje. Šalia esanti Florencijos geležinkelio stotis pavadinta bazilikos vardu.