Après l'arrivée des Romains, un camp fut construit sur les hauteurs de la vallée. A l'époque, la vallée était habitée par des Gaulois païens; c'est alors qu'un Romain fut envoyé avec ses compagnons pour convertir la région. Trouvant la vallée agréable, ils décidèrent alors de monter une mission. Après quelques années, le Romain se maria avec une gauloise qu'il avait convertie, appelée Merca. Pour convertir les païens, le Romain installa un tronc d'arbre sous un tumulus, qu'il déclara autel de la Sainte-Trinité. Bozo fit alors construire une petite église au-dessus de l'autel et organisa la christianisation de la région autour de ce lieu de culte.
Comme c’est le cas dans beaucoup de légendes monastiques, la légende de la fondation de l’abbaye de Fécamp comporte, elle aussi, un épisode dans lequel intervient miraculeusement un grand cerf.
Dans son Histoire de l’abbaye de Fécamp, Léon Fallue nous le relate ainsi :
"Suivant la chronique de l’abbaye de Fécamp, le territoire de cette ville, encore au berceau, fut donné à un comte de race tudesque, nommé Anskise ou Anségise; cet étranger, qui était gouverneur du pays de Caux, faisait ordinairement sa résidence à Fécamp, ce qui porte à croire que cette ville, toute Gallo-Franke, avait succédé à la suprématie de Juliobonna, la romaine.
Anségise ayant découvert, en chassant dans les bois de Fécamp, l’humble oratoire élevé par le Romain, prit la résolution de le remplacer par un édifice plus digne du culte auquel il était destiné. Jusqu’ici, rien de plus naturel ; mais les légendes racontent que ce lieu lui fut indiqué par un cerf blanc, poursuivi par ses chiens, lequel s’arrêta près de cette chapelle, fit face aux chasseurs, sans que ceux-ci, ni leurs chiens, pussent s’en approcher. Elles ajoutent qu’Anségise, surpris de cette nouveauté, mit pied à terre pour étudier les mouvement du cerf, et que cet animal ayant fait à petits pas un cercle autour du lieu où il s’était arrêté, comme pour tracer les fondements d’un édifice, disparut aussitôt à tous les yeux."
Est-ce le grand cerf apparu à Anségise que les bâtisseurs de l’abbatiale ont voulu représenter lorsqu’ils ont sculpté la tête d’un cervidé en surplomb sur la tour lanterne ?
Ou simplement ont-ils voulu représenter cet animal particulièrement mythique dans la pensée médiévale ? En effet, si la symbolique antique du cerf est complexe, il est essentiellement, au Moyen Âge, reconnu comme symbole du Christ ; il serait aussi l’ancêtre mythique des rois de France.
Cette effigie grandeur nature, que le passant attentif peut observer sur la face orientale de la tour, reste mystérieuse, et aucune des études publiées sur l’abbaye ne l’évoque. Son style semble presque naïf, et ses petites cornes font plus penser à celles d’une chèvre ou d’un chamois qu’à la ramure d’un cerf.
La datation de cette sculpture reste elle aussi inconnue. Quatre hypothèses peuvent être formulées :
L'abbaye de Fécamp est née durant la grande vague d'implantations monastiques qui émaillèrent le VIIe siècle (Jumièges, Fontenelle, Noirmoutier, etc.). C'est une communauté de moniales qui s'y installa, afin de parfaire l'évangélisation de la région. La construction du sanctuaire débuta vers 659 autour de la relique du Précieux Sang, confiée selon la légende à la mer par Isaac, fils de Joseph d'Arimathie, et venue s'échouer miraculeusement sur les plages du Pays de Caux. Fécamp se rattache donc à la lignée des sites mythiques intimement liés au Graal. En 665 la première abbatiale est dédicacée.
À partir du IXe siècle les premiers raids Vikings commencent et l'abbaye est dévastée en mai 841.
C'est aux alentours de l'an 1000 que le duc de Normandie Richard Ier, né à Fécamp, décide de réimplanter une présence religieuse. Des chanoines colonisèrent les lieux. Son fils Richard II parvint à convaincre le réformateur Guillaume de Volpiano, abbé de Saint-Bénigne de Dijon, de l'aider à rétablir une communauté monastique digne de ce nom. Peu après, Volpiano arrivait à Fécamp avec une poignée de moines clunisiens. Volpiano instaura la règle bénédictine et fonda le monastère bénédictin de Fécamp. Il ne reste rien de cette église, néanmoins il reste des textes ayant survécu à la dispersion de la bibliothèque de l'abbaye de 1789. Le récit de la construction de la première église donné par Dudon de Saint-Quentin est incontestablement la source la plus connue. Le chanoine décrit l'édifice comme une église à plusieurs tours, faite en pierre et en brique, voûtée ou pourvues d'arcs en deux endroits, blanchie à l'extérieur et peinte à l'intérieur. D'autres sources indiquent qu'un autel dédié au Sauveur se trouvait derrière le maître-autel dédié à la trinité. D'après la chronique de Saint-Bénigne, écrite entre 1058 et 1066, elle placerait le tombeau de Guillaume de Volpiano devant l'autel Saint-Taurin, alors que certains textes comme la vita willelmi le place au centre de l'église; selon d'autres sources encore, le tombeau aurait été situé sous l'église dans une "crypte". Cependant, des fouilles menés en 1925 confirment par l'intermédiaire de sondages la présence sous les travées deux et trois la présence d'une profonde quantité de remblais constitué de fragment d'enduit peint dans lesquels les fouilleurs virent la confirmation de l'existence des peintures murales mentionnées par Dudon. A partir de ces fouilles et de regroupement de textes, Hans Reinhardt et Etienne Fels puis Annie Renoux arrivèrent à prouver alors que l'autel Saint-Sauveur aurait été situé à l'étage de la construction tandis que l'autel Saint-Taurin et le tombeau de Guillaume de Volpiano étaient situé dans une crypte sous l'église.
À Pâques de l'année 1066, Guillaume le Conquérant installe sa cour à Fécamp après que l'abbé de Fécamp a financé la conquête de l'Angleterre par Guillaume. En 1106, après que le précieux sang est devenu un grand lieu de pèlerinage, l'abbaye est agrandie avant d'être dévastée par la foudre en 1168. Une nouvelle église gothique fut alors construite par l'abbé Henry de Sully ; elle est achevée au XIIIe siècle.
Au XVIIIe siècle, les moines de Saint-Maur s'installent et construisent un nouveau portail.
À la Révolution, le monastère fut totalement dévasté et les derniers religieux partirent peu après.
En 1960, un vote est organisé pour savoir si la façade datant du XVIIIe siècle doit être détruite pour mettre au jour la façade du XIIIe siècle.
En 2007, un grand projet de restauration commence qui durera trois ans. La même année voit une grave dégradation sur le tabernacle abritant le Précieux-Sang, la tête de la Vierge présente sur l'acrotère droit étant brisée.
Les armes de l'abbaye, dans les derniers temps, se composaient de deux écus accolés, réunis par la couronne royale, et surmontés de la mitre et de la crosse. Sur l'un des écus étaient trois mitres, pour rappeler, sans doute, les trois abbayes de Notre-Dame de Bernay, de Sainte-Berthe de Blangy (dans le boulonnais), et celle de Saint-Taurin d'Évreux, qui dépendaient des abbés de Fécamp; sur l'autre, portant le mot pax, on remarquait une fleur de lis en tête, et, en point, les trois elous de la passion, le tout orné d'une couronne d'épines, en mémoire du précieux Sang.