Le site de l'abbaye (Aureavalle) était déjà occupé à l'époque mérovingienne. Une chapelle avait été construite au X siècle et en 1070 un groupe de bénédictins venu d'Italie vint y bâtir une église et un couvent. C'est Arnould, comte de Chiny qui leur avait donné les terres.
Au bout d'une quarantaine d'années, ces moines quittèrent les lieux et une communauté de chanoines réguliers, arrivée au début du XII siècle, acheva les travaux. L'abbatiale, dédiée à Notre-Dame, fut inaugurée le 30 septembre 1124 par l'évêque de Verdun, Henri de Blois. Elle mesurait 53 mètres de long et 25 mètres de large.
En mars 1132, des moines cisterciens de l'abbaye de Trois-Fontaines en Champagne vinrent s'associer aux chanoines et construisirent un monastère conformément aux traditions de l'Ordre de Cîteaux. Durant les siècles suivants, l'abbaye connut des périodes prospères et des moments de grandes difficultés car, située à la frontière entre le royaume de France et l'empire, Orval eut à subir les conséquences des guerres et conflits du XV siècle au XVII siècle. Ainsi, pendant la Guerre de Trente Ans, le 2 août 1637, l'abbaye fut pillée et incendiée par les soudards du maréchal de Châtillon. Heureusement la période qui suivit fut un peu plus paisible sur le plan politique et la communauté retrouva la prospérité sous la direction de l'abbé Charles de Bentzeradt.
Au XVIII siècle, Orval, située sur un cours d'eau au cœur d'une vaste forêt, a pu développer une industrie sidérurgique exemplaire.
Lors de la Révolution française, en 1793, les troupes du général Loison incendièrent l'abbaye et la communauté fut dispersée.
Le site resta en ruine jusqu'en 1926, quand un moine de l'abbaye de la Trappe, Marie-Albert van der Cruyssen, entreprit la reconstruction de l'abbaye et la restauration des ruines. L'abbatiale actuelle a été consacrée le 8 septembre 1948.