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 Solutore, Avventore e Ottavio, precedentemente conservate nell'Abbazia di San Solutore maggiore, fuori dalle mura. Durante gli scavi per le fondamenta della chiesa dei SS. Martiri furono rinvenute una gamba bronzea di legionario e una zampa di cavallo, anch'essa in bronzo, (conservati presso il Museo di Antichità di Torino) parti di un monumento equestre romano probabilmente collocato nei pressi del vicino foro. Si trattava forse di Caio Valerio Clemente, patrono della città, al quale sappiamo che furono dedicate due statue (ne sono state rinvenute le lapidi dedicatorie), oppure di Glizio Attilio Agricola, del quale si possiede una lapide "clipeata", ossia di un genere che poteva ornare i monumenti equestri.

Solutore, Avventore e Ottavio, forse appartenenti alla mitica  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 (martyrion) ad opera di S. Giuliana di Ivrea (le cui impronte sul marmo [vedi immagine qui sotto] - probabilmente un manufatto medievale - 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 vi fondò un monastero: il complesso prese il nome di Abbazia di S. Solutore (nel 2011 ne sono emerse le  tracce archeologiche). 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.