Au Moyen-Âge, Gréoux avait deux églises, il semblerait que la première ait été Saint-Pierre aux Liens, située à l'emplacement de l'ancienne agglomération romaine, près des thermes. En effet. depuis des temps immémoriaux, cet endroit était un lieu de culte antique, rattaché aux résurgences des eaux tenues pour sacrées. Le nom de Gréoux viendrait d'ailleurs du nom de la déesse Grysélis nymphe des eaux curatives.
L'église Saint-Pierre fut un lieu de culte jusqu'au début du dix-septième siècle, époque où elle fut désaffectée et ruinée.

La deuxième, qui est l'église actuelle, était construite dans le bourg qui, par suite des invasions diverses, s'était blotti autour du château pour sa protection.
Gréoux faisait partie du diocèse de Riez et l'église Notre-Dame des Ormeaux (des ormes étaient autrefois plantés sur la place) fut donnée à l'abbaye de Montmajour par l'évêque Augier de Riez en 1096. Cette abbaye possédait déjà des biens sur ce territoire depuis la fin du dixième siècle : en 960, Berthe, veuve du comte d'Arles, donne à Montmajour un domaine sis à Gréoux. En 963, le pape Léon VIII confirme cette donation. L'installation de l'église actuelle de la cité, confirmée par les droits de l' évêque de Riez, se situe en 1227. La construction effective de cet édifice s'étend de la fin du onzième au milieu du douzième siècle. L'église subit diverses transformations aux quatorzième, quinzième et dix-huitième siècles, elle fut gravement endommagée en 1574 par les calvinistes. Sous la Révolution, elle fut achetée par un particulier Antoine Blanc qui la sauva. Elle fut réparée en 1829 et reconsacrée le 26 juillet 1831 par Monseigneur de Miollis, évêque de Digne (celui dont parle Victor Hugo dans les Misérables sous le nom de Myriel). Depuis, une grande restauration eut lieu de 1973 à 1975, donnant l' aspect actuel.

Église romane, dont l'austérité est renforcée par son aspect trapu dû à la déclivité du terrain, cet édifice a connu des transformations aux quinzième, seizième et dix-huitième siècles dans un esprit gothique. Le clocher en forme de tour carrée a été édifié en 1821 avec les pierres des remparts et en particulier celles du portail Saint-Sébastien qui donnait accès aux Aires. Il a remplacé un « clocher mur » qui se trouvait rue de l'église (voir le mur à gauche de l'église).

Le portail semble être du treizième siècle, la porte aux très longs claveaux est surmonté d'un vaste oculus. La porte latérale est certainement le portail primitif. En entrant, on est surpris de voir la nef aussi vaste, on est séduit par les proportions harmonieuses de ce vaisseau en plein cintre, renforcé de doubleaux, que l'extérieur ne laisse pas soupçonner. Le décapage des murs a révélé l'hétérogénéité des constructions. Les trois travées précédant le chœur présentent un berceau en grès tendre, les deux travées basses des moellons moins soignés (agrandissement postérieur).

Le chœur moins élevé que la nef porte une croisée d'ogives de style gothique, la clé est sculptée aux armes de l'Agneau Pascal. Au Moyen-Âge, des chapelles latérales furent construites. Elles on été transformées en bas-côté par le percement des murs latéraux (voir l'inégalité des arcs). Les deuxième, troisième, quatrième travées remonteraient aux quatorzième et quinzième siècles. Leur voûte est gothique. Dans le parement de la deuxième on peut observer un fût de colonne antique en remploi et deux piliers polygonaux dont un est surmonté d'un chapiteau à crochets. La clé pendante de la quatrième conserve les armes très effacées d'un prélat.

La chapelle de la Vierge, mieux articulée à la nef, semble dater du seizième siècle, elle forme l'amorce d'un faux transept. La voûte est gothique. Le bénitier en marbre est l'ancienne cuve baptismale, elle date de 1880 environ.