La première implantation religieuse à Orval remonte au IX eme siècle. Des moines Bénédictins venus de Calabre en 875 y fondèrent un premier monastère. Le nom d'Orval n'existait pas encore.

L'origine du nom Orval vient d'une phrase que prononça Mathilde, Duchesse de Basse Lorraine.

Mathilde était comtesse de Toscane lorsqu'elle épousa Godefroy Le Bossu. Oncle de Godefroy de Bouillon, il portait le titre de Duc de Basse Loraine. Leur hyménée fut couronnée par la naissance d'un fils. Cette union heureuse dura un peu plus de huit ans. Le compte de Flandre, alors en opposition à Godefroy Le Bossu, fomenta un attentat contre le Duc et le fit assassiner.

Mathilde, encore jeune, se trouva donc veuve avec un enfant de bientôt huit ans. Hélas, le destin s'acharna sur la belle comtesse. Au cours d'une promenade, son fils, glissa dans les eaux glacées de la Semois et se noya.

Accablé par la douleur, Mathilde vivait enfermé et ne s'octroyait que de rares sorties dans les forêts alentours. C'est au cours de l'une de ses rares promenades qu'elle découvrit, proche d'un monastère, une fontaine naturelle d'où coulait une eau froide et limpide. Cette fontaine donnait naissance à un petit ruisseau dans lequel venaient frayer truites et autres poissons de rivières.

Mathilde se pencha vers le bassin que formait la fontaine et plongeant la main pour y puiser de l'eau, découvrit avec effroi que son anneau nuptial, dernier souvenir de son défunt époux, avait glissé de son doigt et était tombé dans le fond du bassin. La limpidité de l'eau donnait une impression de faible profondeur, mais ce n'était qu'illusion. Ne pouvant atteindre son précieux bijou, Mathilde, la mort dans l'âme, pria Notre Dame pour que lui soit rendu son anneau.

C'est alors qu'un événement incroyable se produisit ! Bondissant de l'eau, d'un saut puissant, une truite aux multi couleurs tenait dans sa bouche l'anneau nuptial si cher au cœur de Mathilde. La truite envoya l'anneau dans le creux de la main de la jeune femme.

Mathilde, émerveillé par le miracle dont elle avait été témoin s'écria : " Ce lieu est un Val d'Or ! ".

C'est en hommage à cet événement et à Mathilde que le monastère fut baptisé Orval. C'est toujours en souvenir de ce moment que les armes de l'abbaye d'Orval montre une truite portant un anneau d'or dans la bouche.