La plus ancienne description de cette église remonte à 1053, lorsque les reliques de saint Wulfran (aussi appelé saint Hermeland) furent accueillies à Rouen. Elle devait toutefois exister avant la fin du VIII^e siècle. La relation étroite qui existait entre l’église et la Métropole incite à penser à une fondation sous les épiscopats de Hugues (vers 722-730)
La plus ancienne mention de la paroisse remonte à 1117. Il y est question du prêtre. Il s’agissait d’une dépendance de la cathédrale, sous l’autorité des chanoines.

Les travaux se terminèrent vers 1556. A cette date on dorait encore les statues des portails.
St-Herbland fut dévastée par les Huguenots en 1562.
Les dessins de Jacques Le Lieur comme les autres images de l’église montrent que l’église St-Herbland présentait des similitudes avec l’église St-Maclou sa contemporaine. Les moulures prismatiques des archivoltes descendaient directement jusqu’aux bases sans aucun chapiteau. L’intérieur était fort clair du fait de l’importance de la surface vitrée. Il y avait une nef assez haute, plus longue que ne le laisse penser le dessin de Le Lieur, et deux bas-côtés. Les clefs de voûte étaient ouvragées. Celles du chœur étaient dorées.

Le chevet se trouvait sur la rue des Carmes. A l’ouest, le pignon s’appuyait sur des maisons. Comme dans certaines églises de Rouen, le portail principal (construit vers 1530-1531) s’ouvrait sur la rue du Gros-Horloge (rue Courvoiserie au moyen âge) et une petite porte s’ouvrait au nord, vers l’aître. Il y avait quatre chapelles dédiées à saint Jacques, saint Matthieu, sainte Catherine et saint Louis.
Un svelte petit clocher en bois recouvert de plomb s’élevait au milieu de l’église.
L’église paroissiale fut supprimée en 1791. Elle fut vendue le 6 messidor an IV (24 juin 1796). L’acheteur, François Moulin, la paya 112.850 livres. Elle était en mauvais état et, en 1799, il fut sommé par la Municipalité de faire disparaître les ornements du portail.
L’édifice fut transformé en établissement de messagerie, accueillant les diligences et servant de remise.
En 1824-1825, un immeuble fut construit à l’emplacement de l’église par l’architecte Maillet du Boullay. Une simple galerie marchande à angle droit, pratiquée dans le nouveau bâtiment, fut appelée passage St-Herbland.