Le terrain retenu est donc situé au fond du Vieux-Port, à proximité du plan Fourmiguier, zone occupée par les chantiers de construction navale, puis par l'arsenal des galères. La construction de l'église est d’autant plus délicate qu’elle se trouve sur des terrains alluvionnaires et des remblais instables de l’ancienne corne du port qui s’est envasée au Moyen Âge et dont l’extrémité est visible dans le jardin des vestiges.
Cette construction se fera sur une longue période. Les travaux commenceront très lentement en 1447. Les Augustins utilisèrent le bois d’une galère hors d’usage cédée par Jean de Villages, neveu de Jacques Cœur, pour réaliser la charpente. Les travaux sont cependant suffisamment avancés pour accueillir le pape Clément VII venu accompagner sa nièce Catherine de Médicis qui vient épouser le deuxième fils du roi de France qui sera ultérieurement couronné roi de France sous le nom d’Henri II.
La consécration de l’église est effectuée le 15 janvier 1542 par Barthélemy Portolenqui, évêque de Troyes,alors que la nef n'est couverte que d'une simple charpente de bois. Pour certains historiens cela est une preuve des difficultés financières rencontrées par les Augustins, tandis que pour d’autres cela reflète simplement leur esprit de pauvreté.
L'église Saint Ferréol qui se situait à l'extrémité de la rue de ce nom, à l'emplacement de la place Saint Ferréol, avait été démolie en 1794. En 1803 l'évêque Champion de Cicé transfert le vocable de Saint Ferréol à l'église qui portera désormais le nom composé de « Saint Ferréol les Augustins ».
En 1840 l'église est à nouveau menacée par la construction à son emplacement d'un hôtel des douanes. La création de la rue impériale, actuelle rue de la République, faillit également lui être fatale. Il n'en fut rien, au contraire, car si les travaux ébranlèrent l'édifice, ils permirent de dégager sa façade qui donne désormais sur le port grâce à la destruction d’immeubles situés au bas de cette nouvelle rue. La façade est reconstruite en 1874 dans un style néo-classique puis recouverte en 1875 d'un placage en ciment réalisé par Joseph Letz.
Le 8 juillet 1791 le conseil de la commune propose la démolition de l'église car sa vente aurait rapportée beaucoup d'argent à cause de son emplacement à proximité du port. Peu de temps après, le 16 août 1791, un décret de l’assemblée constituante fait de l'église le siège d’une paroisse qui prend le nom de Saint Augustin. L’architecte Ponge dresse plusieurs projets dont celui de 1793 qui consiste à prolonger la partie inférieure de l’ancienne rue des Augustins en démolissant la partie est de l'église. La cinquième travée sera donc supprimée. De même le couvent est rasé à l'exception de sa partie contiguë au chœur de l'église et au clocher, afin de permettre la création d'une nouvelle voie qui prendra le nom de rue neuve des Augustins puis rue des Augustins lorsque l’ancienne rue des Augustins sera rebaptisée rue du Beausset. Des immeubles seront construits entre cette nouvelle rue et la place cul-de-bœuf actuellement place Gabriel Péri.
L'église est vendue le 20 juillet 1796 au négociant Charles Guinot qui est ensuite déchu de ses droits pour ne pas avoir payé le prix demandé. Le 9 avril 1799 l'édifice est mis à la disposition du service des fourrages. C'est vers 1801 que furent réalisés les travaux de démolition de la cinquième travée et la construction d’une nouvelle façade.