Molt a prop del puig de Privàlloc conquerit a la darreria del segle XI pel comte Ermengol IV d’Urgell—fou fundada, abans de l’any 1166 i pel comte Ermengol VII d’Urgell, la Villam Novam de Privadano, que correspon a l’actual poble de Vilanova de les Avellanes o de la Sal.
L’existència d’una carta de poblament, que no s’ha conservat, s’infereix de l’acta fundacional del monestir de Bellpuig de les Avellanes, instituït pels comtes d’Urgell Ermengol VII i Dolça el 1166; en aquest document, entre moltes altres donacions, els esmentats comtes i fundadors del cenobi li cediren la Vilanova de Privà, la qual, segons l’escriptura, noviter edificavimus.
Tot i que no es faci referència explícita a la fundació i la construcció d’una església, és raonable considerar que dins la nova població s’hi devia bastir un temple, segurament amb funcions parroquials, el qual estaria dedicat a santa Maria, com l’actual. En tenim una primera referència en la dècima del 1391. L’església de Vilanova de les Avellanes és avui dia un edifici molt modificat, refet al segle XVIII dins l’estil barroc, i és molt difícil verificar si alguna part de la construcció correspon a l’època romànica. A l’inici del segle XIX van ser traslladades a aquesta església algunes peces del temple romànic de Santa Margarida de Privà.