La chiesa di Santa Caterina sorge dove fino al 1732 si trovava la piccola chiesa di San Secondo della Torre Rossa, romanica a tre navate con portichetto in facciata e chiostro sull'ala meridionale, costruita probabilmente poco prima del 1070, anno in cui il nome della chiesa e del convento omonimo, compaiono la prima volta in un documento originale riferito alla donazione del convento fatta dalla contessa Adelaide di Susa e Pinerolo ai monaci benedettini dell'Abbazia di San Benigno di Fruttuara nel Canavese.
In seguito alla donazione della contessa Adelaide, San Secondo della Torre Rossa venne retta dai monaci benedettini “neri” di Fruttuara, che provvidero anche a trasformare in campanile la torre romana attigua alla chiesa, sopraelevandola di due piani, e che ressero il priorato fino a circa la metà del secolo XIV, quando fu trasformato in commenda da Papa Sisto IV che la concesse al nobile Pietro Fantono e poi passò alla famiglia Baiveri.
Verso il 1550 la chiesa sprovvista di religiosi fu affidata dall'allora priore commendatario Nicola Baiveri, nobile astigiano, ai Padri Servi di Maria dell'Ordine di S. Agostino, privati, per ragioni militari a causa delle guerre per far posto a nuove fortificazioni, della chiesa e convento di Santa Caterina che sorgeva già dal 1273 vicino al Borgo di San Marco, presso la porta di Sant'Antonio.
Fu così che alla chiesa di San Secondo della Torre Rossa, venne aggiunto il titolo di S. Caterina Regina e Martire da Alessandria d'Egitto.
Nel 1604 il Priorato di San Secondo della Torre Rossa venne secolarizzato da Papa Clemente VIII, con Bolla del 15 giugno e con istanza del duca di Savoia Carlo Emanuele I.
Si arrivò così ad una convenzione tra i Padri Serviti e l'Ordine religioso militare di San Maurizio e Lazzaro di Torino, nuovo commendatario ed attuale proprietario del complesso barocco.
Nel 1613 fu investito della commenda il cavaliere Mauriziano don Domenico Coardo.
Nell'agosto del 1732, i Padri Serviti si videro costretti ad abbattere l'antica chiesa romanica, oramai in stato rovinoso, e celebrare la S. Messa nella sacrestia, in attesa di ottenere dall'Ordine Mauriziano l'autorizzazione e i fondi necessari alla ricostruzione.
Le speranze dei Padri astigiani vennero disattese, nonostante le suppliche a Carlo Emanuele III, Gran Maestro dei Cavalieri mauriziani. In attesa della costruzione della nuova chiesa nel 1735 i Padri Serviti fecero ornare il frontone e gli stipiti del portone del convento, divenuto unico passaggio per la sacrestia adattata a celebrare le funzioni.
Sul frontone del portone venne scolpito uno stemma su cui sono raffigurati una bilancia e un cane. Finalmente, nel 1766, dopo nuove istanze dei Padri Serviti, da Torino giunse il progetto della nuova chiesa firmato dall'architetto Giovanni Battista Ferroggio di Camburzano, nel vercellese. Dopo una breve sospensione dei lavori per mancanza di fondi nel 1771, la ricostruzione riprese nell'ottobre del 1772 per terminare l'anno dopo grazie all'opera dell'impresario Giovanni Battista Piazza.
La chiesa venne aperta al culto il 26 aprile 1773 dal Vescovo Mons. Paolo Maurizio Caissotti e consacrata solennemente il 14 settembre 1818 dal Vescovo di Asti Mons. Antonino Faà di Bruno, morto il 10 novembre 1829 e sepolto nella tomba del convento attiguo alla chiesa; le spoglie furono poi traslate nel 1850 all'interno della chiesa dietro all'Altare Maggiore.
Dopo la soppressione degli ordini religiosi del 20 gennaio 1801 dovuto al Decreto del Governo Repubblicano francese, e venuto a mancare anche l'ultimo dei padri Serviti, il 3 febbraio 1850 la chiesa fu affidata dall'Ordine Mauriziano ai Frati Minori Osservanti di San Francesco che abbandonarono così il monastero del Gesù (Opera Pia Michelerio), che occupavano dal 1827.
Nel 1888, a causa della malattia del padre reggente, la parrocchia cessò di appartenere ai Frati Minori, che la ripresero poi dal 4 febbraio 1929 fino al 1967, quando subentrarono nella cura della Parrocchia i Padri Oblati di San Giuseppe di Asti che la ressero fino al 2000, oggi è amministrata dalla Diocesi di Asti.
La chiesa di S. Caterina è la sola chiesa astigiana ad essere stata compresa nell'importante catalogo della Mostra sul Barocco Piemontese del 1963.