El lloc de la Nou és documentat des de l’inici del segle XI. Un dels primers esments es troba en una escriptura datada l’any 1011 quan és citat “ipsum kastelar que dicunt Nuce”, com a afrontació territorial del castell d’Albinyana.
L’església de Santa Magdalena de la Nou, com també la d’Altafulla, havia depès a l’inici del segle XII de l’única parròquia de la contrada, la de Tamatit, que és citada en la butlla que el papa Anastasi II atorgà l’any 1154 a l’església de Tarragona. Posteriorment, en un any imprecís entre el 1154 i el 1194, l’església parroquial d’Altafulla nasqué en deslligar-se de la de Tamarit; consta ja esmentada com a parròquia en la butlla del papa Celestí III concedida a la metròpoli tarragonina el 1194. Hom sap que des de llavors tingué com a sufragània l’església de Santa Magdalena de la Nou de Gaià, integrada dins el seu terme.
Després d’alguns segles de buit documental, hi ha notícia que l’església de Santa Magdalena l’any 1772 fou erigida en vicaria mutual de la parròquia altafullenca, situació que perdurà fins el 1816. Anys més tard, sense que es pugui especificar cap data concreta, l’església de la Nou de Gaià esdevingué parròquia independent pertanyent a l’arquebisbat de Tarragona.
La parròquia actual de Santa Magdalena fou bastida al segle XVIII en el mateix indret que havia ocupat el temple medieval precedent.