Vers 1047, selon Orderic Vital, Guillaume de Normandie épouse Mathilde de Flandre^{[AB 1]}. Mais le pape Léon IX l'interdit au concile de Reims tenu en octobre 1049^{[AB 2]}, prenant comme prétexte que les deux époux seraient parents à un degré interdit par le droit canonique^{[note 1]}. Le mariage peut toutefois être accepté par le pape si une dispense est demandée, ce que Guillaume n'a pas fait.

L'archevêque de Rouen Mauger, son « demi oncle » (fils de Richard II et de la concubine Pépia), qui était son tuteur et qui apprécie peu de perdre son tutorat, lance une excommunication contre le couple^{[AC 1]}. En 1059, Lanfranc de Pavie, écolâtre de l'abbaye du Bec, principale personnalité intellectuelle de Normandie, est envoyé à Rome^[] pour négocier le pardon auprès du pape Nicolas II^[]. Michel de Boüard est allé à Rome pour rechercher les preuves de l'excommunication papale, et n'a pas trouvé trace de sanction. Le couple est officiellement marié en 1053 selon Grégoire de Tours ou en 1063 selon Orderic Vital^[].

Il existe d'autres raisons politiques à la fondation de l'abbaye. Guillaume est le fils de Robert I^er de Normandie, dit le Magnifique, et de sa concubine ou épouse more danico, Arlette. Il est présenté officiellement aux barons en 1034 avant le départ de son père en pèlerinage à Jérusalem. Robert meurt en juillet 1035 à Nicée, sur la route du retour, et Guillaume, alors âgé de sept-huit ans seulement, devient duc de Normandie. Sa légitimité est fragile et il doit combattre pendant toute la première partie de son règne les barons de Normandie, qui le considèrent comme bâtard. Le duc remporte une victoire importante en 1047 à la bataille de Val-ès-Dunes, à une douzaine de kilomètres au sud-est de Caen. Lors de la bataille de Varaville, à moins d'une vingtaine de kilomètres au nord-est de Caen, en 1057, le duc remporte une victoire décisive. Ces batailles l'inclinent fortement à construire une importante place forte au centre du duché en même temps qu'un glacis sur les frontières bretonnes. Il cherche donc à asseoir davantage son autorité sur la basse Normandie où la rébellion a été la plus forte.

Cela passe par la construction de châteaux, mais également par la fondation d'abbayes, selon un schéma classique en Normandie depuis le X^e siècle^[]. Le duc décide donc de densifier le réseau d'établissements monastiques en Basse-Normandie, alors beaucoup plus lâche que dans la vallée de la Seine mieux contrôlée par les ducs de Normandie. Ce mouvement permet ainsi de combler le vide laissé par les raids Vikings dans cette région où de nombreux établissements préromans n'ont pas survécu, et où les fondations nouvelles tardent à s'épanouir^[].

L'abbaye aux Hommes et l'abbaye aux Dames, fondée à l'est de la ville, ont toutefois dans ce dispositif une place privilégiée. En effet, sur les dix-huit abbayes élevées durant le règne de Guillaume le Conquérant, seules deux, celles de Caen, sont fondées directement par le duc lui-même, les autres étant créées par des seigneurs locaux et reconnues ensuite par le duc^[]. La fondation des deux abbayes caennaise, en plus de celle du château de Caen, s'inscrit donc dans un dessein politique plus large qui vise à faire de Caen un point d'appui plus proche de la sédition que Rouen qui se trouve dans la partie orientale du duché. En choisissant de s'y faire inhumer — en 1083 à l'abbaye aux Dames pour Mathilde de Flandre et en 1087 à l'abbaye aux Hommes pour Guillaume le Conquérant — Guillaume et Mathilde inscrivent dans la durée l'attention des ducs-rois non seulement pour l'abbaye, mais également pour la ville de Caen qui, d'un gros bourg de constitution anarchique, devient la capitale secondaire de la Normandie^[]. Les descendants de Guillaume confortent ensuite le lien des deux abbayes avec la dynastie ducale et royale. Ainsi, fait exceptionnel, Guillaume le Roux dépose les insignes royaux (couronnes et sceptres) de ses parents aux trésors des deux abbayes où ils sont inhumés^[].

Vers 1064, selon Orderic Vital, Guillaume décide de la fondation d'une abbaye^[] qu'il dédie à saint Étienne, premier martyr^[]. L'abbaye Saint-Étienne de Caen, « SANCTS STEPHANUS CADOMEUSIG », est placée sous la règle de saint Benoît^[]. Elle est couramment nommée abbaye aux Hommes pour la distinguer de l'abbaye de la Sainte-Trinité, dite aux Dames, établissement de bénédictines fondé à la même époque à l'est de la ville.

L'abbaye est implantée à l'ouest de la ville de Caen. Certains textes anciens affirment que l'abbaye a été implantée à l'emplacement d'une chapelle Saint-Étienne plus ancienne^[]. Le choix de ce site peut en effet interroger. Situé à proximité de l'Odon, le terrain est marécageux et le sol instable. Mais la présence de ce lieu de culte plus ancien n'est seulement qu'une hypothèse sans source écrite crédible ou archéologique pour la corroborer. Est ainsi créé un quartier nouveau, le Bourg-l'Abbé qui se trouve sur des terrains de paroisses appartenant à la cathédrale de Bayeux. Cette dernière les cède à la reine Mathilde de sorte que les moines de l'abbaye aux Hommes se trouvent sous la dépendance spirituelle de l'abbesse de Caen. C'est pour se soustraire à cette dépendance qu'ils construisent l'église Saint-Nicolas de Caen pour les paroissiens du Bourg-l'Abbé^[]. En 1083, soixante-douze maisons sont recensées dans le bourg^[].

Le duc confie la construction à Lanfranc qui avait donné son avis au bienheureux Herluin pour la reconstruction de l'abbaye Notre-Dame du Bec. Il le nomme abbé de Saint-Étienne le 15 juin 1066^[] et archevêque de Cantorbéry en 1070^[]].

En 1066, Guillaume, désormais roi d'Angleterre, dote l'abbaye d'une charte^]. La fondation est reconnue par une bulle pontificale d'Alexandre II en 1068^[].