On ne connaît rien des édifices qui ont précédé celui de la fin du moyen âge et de la Renaissance. Il dut être endommagé par la guerre et le siège de la ville au début du XV^e siècle. Il fallut attendre la paix retrouvée pour que, alimenté par des indulgences et par des contributions volontaires des paroissiens, un incessant chantier mené de 1458 à 1530, aboutisse à un chef-d’œuvre d’architecture.
Entre 1458 et 1471, ont construisit la nef, la chapelle St-Nicolas et le portail nord.
En 1470, un marché fut passé avec le célèbre maître-maçon, Ambroise Harel. C’est certainement à lui que l’on peut attribuer la conception générale du chœur.
Le portail occidental avait été commencé en 1460. On l’attribue aussi à Ambroise Harel.

XVIII^e siècle, on terminait au nord les voûtes du croisillon du transept et le deuxième bas-côté de la nef.
L’église St-Vincent présentait un aspect pittoresque et irrégulier s’expliquant par les circonstances, et la longueur, de sa construction. Le chœur avait été construit d’un seul jet. Il était soutenu par des contreforts dont certains étaient à double volée. Intérieurement haut de 23 mètres, il était spacieux et clair. Supporté par dix colonnes cylindriques, il était entouré d’un déambulatoire sur lequel s’ouvraient des chapelles. Celle dans l’axe était vouée à la Vierge. Entre les arcs et les fenêtre hautes courrait un triforium ouvragé.
La tour construite sur le transept était de style gothique flamboyant, quoique construite dans la deuxième moitié du XVII^e siècle. Ce n’était pas une tour lanterne comme à St-Maclou. Elle se terminait en terrasse.

Le portail nord du transept n’était semble-t-il pas accessible avant le XIX^e siècle. Il ne présentait pas de disposition particulière. Le portail sud, lui, était du plus grand intérêt par la richesse de ses ornements.
Le portail principal s’ouvrait sans le pignon occidental. Il débouchait dans l’aître (le cimetière) St-Vincent, qui lui-même donnait sur la rue de la Vicomté. Il était précédé d’un porche ajouré, voûté en pierre, au-dessus duquel il y avait un appentis en charpente destiné à recevoir les soufflets de l’orgue. Le pignon qui le surmontait n’était pas percé d’une rose, mais d’une grande fenêtre, comme pour les pignons des bas-côtés.
La nef avait peu d’ampleur, deux travées seulement, mais possédait des doubles collatéraux.
En 1791, l’église St-Vincent fut conservée avec douze autres églises paroissiales. Elle s’enrichit alors de dépouilles provenant d’églises supprimées, comme l’ancienne horloge de l’église St-Martin-du-Pont, ou, en 1862, les portes de l’église St-André sa voisine.
Fermée en 1793, elle avait été rachetée par la famille Ribard. Elle la préserva soigneusement pendant plus de 18 mois avant de la rendre au culte.
En 1802, l’église fut officiellement retenue comme succursale puis, en 1829, comme église paroissiale.
La Seconde Guerre Mondiale fut fatale à St-Vincent. Elle avait déjà été sévèrement touchée le 19 avril 1944, mais, après les premiers incendies du 30 mai dans la rue Jeanne d’Arc, l’édifice vit toutes ses voûtes s’effondrer le 31 mai sous les bombes alliées, qui, entre 11 heures et midi, frappèrent d’abord la tour carrée et le chœur avant d’anéantir la nef et la façade.

Seul le Grand Christ, intact, dominait encore les ruines de l’église anéantie.
Après la guerre, le quartier a été entièrement restructuré. Une nouvelle voie, la rue du Général Giraud, traverse l’emplacement de l’église. Aurait-elle pu être sauvée ? Les conditions qui étaient celles de l’époque ont fait répondre non. En 1947-1948 on rasa les vestiges, ne laissant en place qu’une partie du pignon méridional du transept et un morceau de mur. Plus tard, quelques pierres incrustées dans le trottoir marquèrent une petite partie du plan de l’édifice.