La chiesa primitiva era dedicata a Santo Stefano ed esisteva fin dal X secolo: la soppressione del titolo avvenne nel 1575 e due anni dopo venne posata la prima pietra della chiesa attuale, destinata a ricevere le reliquie dei martiri paleocristiani 73 (Solutore, Avventore e Ottavio), precedentemente conservate nell'Abbazia di San Solutore maggiore, fuori dalle mura. Durante gli scavi per le fondamenta del nuovo edificio furono rinvenute una gamba bronzea di legionario e una zampa di cavallo, anch'essa in bronzo, (conservati al Museo di Antichità) probabilmente parti di un monumento equestre romano collocato nei pressi del vicino foro. Si trattava forse di Valerio Clemente, patrono della città al quale furono dedicate due statue, una equestre ed una a piedi.

Solutore, Avventore e Ottavio, forse appartenenti alla Legione Tebea ma più probabilmente "indigeni", furono martirizzati nella regione di Valdocco verso la fine del III secolo. Solutore riuscì forse a fuggire ad Ivrea, dove però venne raggiunto ed ucciso. Intorno al 286, nei pressi dell'attuale Mastio della Cittadella, sorse a ricordo una piccola cappella (martyrium) ad opera di S. Giuliana di Ivrea (le cui impronte si conservano nella chiesa dei Ss. Martiri, presso l'altare maggiore, dove si può osservare anche il masso sul quale S. Solutore subì il martirio). Nel IV secolo la cappella fu ampliata e nel X secolo sul luogo venne eretta una Basilica, poi rovinata dai Saraceni. Nel 1006 il Vescovo Gezone fonda anche un monastero: il complesso prende il nome di Abbazia di S. Solutore. L'intera costruzione venne rasa al suolo dai Francesi nell'aprile del 1536, ma le reliquie erano già state messe in salvo all'interno delle mura cittadine.

Pagine del trecentesco "Codice della Catena" (Archivio Storico della Città di Torino). Vi sono raffiguranti i tre Santi Martiri insieme ad altri santi cari alla tradizione religiosa torinese. Da sinistra: Sant'Ottavio, San Massimo (il primo vescovo di Torino), Sant'Avventore, San Solutore, San Giovanni Battista, San Secondo. In calce alle pagine campeggiano il toro, simbolo del Comune, e lo stemma crociato dei Savoia.