Venant de Paris, les Augustins Déchaussés voulurent d’abord s’établir à Rouen en 1630 mais le Parlement de la ville s’y opposa d’abord, signifiant aux religieux que, déjà, beaucoup de couvents, pour hommes ou pour femmes, s’étaient installés dans la cité et ses faubourgs. En fait, c’est surtout à la demande des quatre grands ordres religieux mendiants présents à Rouen (les Augustins, les Carmes, les Cordeliers et les Jacobins) que cette première fin de non-recevoir fut transmise aux premiers Augustins Déchaussés. Enfin, en 1633, le roi Louis XIII signa à Forges-les-Eaux les lettres patentes unissant les religieux de la congrégation de St-Paul-Ermite, appelés plus communément les Petits-Pères de la Mort ou moines Paulins, à l’ordre des Augustins Déchaussés (OAD), qualifiés aussi d’Augustins Déchaux ou Réformés, religieux mendiants.

Les Augustins Déchaussés prirent possession du monastère de leurs prédécesseurs, élevé pratiquement au pied de la côte Ste-Catherine. C’était un domaine en dehors de la porte Martainville, dans une zone marécageuse parcourue par de nombreux petits ruisseau et par l’Aubette. Il y construisirent un véritable couvent. L’épouse du roi Louis XIV, la reine Marie-Thérèse d’Autriche, en fut déclarée fondatrice.
Il s’étendait au nord-est de l’esplanade du Champ de Mars actuelle, vers l’entrée de la rue du Faubourg Martainville, là où ont été construits des immeubles.
Le monastère à peine bâti, il restait à élever une église.
L’édifice dont la première pierre fut posée dès le 30 août 1672 fut dédié deux ans plus tard sous le titre de Notre-Dame-des-Victoires. Il reprenait le vocable associé à l’église existant encore du couvent de Paris (place des Petits-Pères). Cette dernière fut consacrée en mémoire du succès des armées de Louis XIV contre les Hollandais et bâtie par les Augustins Déchaussés comme leur implantation principale, établie d’abord dans la capitale vers 1619. Deux chapelles, St-Nicolas-de-Tollentin, dédiée à un saint plutôt invoqué par les malades pour la délivrance des âmes du purgatoire, et Notre-Dame-des-Sept-Douleurs, existaient dans l’église conventuelle de Rouen. De plus, la dévotion mariale attachée à leur ordre étant forte, le 4 mars 1657, une confrérie de Notre-Dame-des-Sept-Douleurs y avait été érigée canoniquement.
Des lettres patentes du 28 novembre 1674 confirmèrent l’établissement religieux des “Petits-Pères”, Augustins Réformés ou Déchaussés (car ces religieux allaient pieds nus dans leurs sandales)