L’església de Sant Fructuós de Tarragona era situada a la part baixa de la ciutat, prop de l’actual plaça de Corsini i de l’antiga basílica del fòrum municipal romà de la ciutat. És esmentada en un document de la darreria del segle XI, donat a conèixer per X. Sitjes; es tracta d’un testament datat el 4 de desembre de 1091 i atorgat pel sacerdot Guillem Geribert, en el qual hi ha notícia que aquest llegà als cenobis de Sant Pau del Camp de Barcelona i a Sancti Fructuosi Tarraconensi un tonell nou amb el vi que contenia, la venda del qual havia de servir per a les obres que es duien a terme en ambdós edificis. Aquest esment tan reculat s’ha de relacionar amb la primera ocupació de la ciutat en època de l’arquebisbe Berenguer Sunifred de Lluçà, que segurament intentà la fundació d’un monestir canonical sota l’advocació de sant Fructuós. Aquest cenobi tingué una vida efímera. L’any 1151, en un judici celebrat entre l’arquebisbe de Tarragona, Bernat Tort, i Robert d’Aguiló, aquest darrer es queixava que el prelat havia expulsat “monachos de ecclesia Sancti Fructuosi”, la qual església li havia estat donada a ell per l’arquebisbe Oleguer. D’altra banda, pocs anys després, en la butlla de confirmació de béns que el papa Anastasi IV concedí, l’any 1154 a l’església tarragonina, hi consta l’ecclesiam sancti Fructuosi.
L’arquebisbe Bernat Tort, el 29 de juny de 1159, decidí fer donació del temple de Sant Fructuós al capítol de la seu perquè es pogués beneficiar de les seves rendes. A la darreria del segle XII, el 1194, l’ecclesiam Sancti Fructuosi figura entre les possessions ratificades a l’església tarragonina en la butlla atorgada aquell any pel papa Celestí III.
Vers el final del segle XIII, el 1274, l’arquebisbe Bernat d’Olivella la va concedir a la dignitat de l’ardiaca de Sant Fructuós, que acabava d’erigir; hi ha referència documental que el 1381 n’era ardiaca Bernat de Sant Dionís i el 1411 l’ardiaca Joan Nadal.
A la darreria del segle XVI, el 1589 els frares caputxins de Tarragona bastiren al costat d’aquesta església llur convent, a la qual traslladaren el Santíssim Sagrament.
Durant la guerra dels Segadors, a mitjan segle XVII, el rei Felip IV volgué fortificar la part baixa de la ciutat i manà enderrocar el temple de Sant Fructuós.
És molt probable, o almenys es pot apuntar com a hipòtesi, que el temple de Sant Fructuós fos bastit o aprofités en part les restes arquitectòniques d’un edifici romà, ja que es construí prop de la zona monumental del fòrum romà de la ciutat. Segons Serra i Vilaró, és possible que Sant Fructuós es construís damunt mateix de la basílica del fòrum municipal de la colònia.