L'origine della chiesa di santo Stefano risale ad epoca paleocristiana (V secolo). Il primitivo edificio venne eretto sull'area della necropoli romana ubicata fuori dalla città di Augusta Praetoria, poco oltre la Porta Principalis Sinistra, dove iniziava la strada per l'Alpis Poenina (ovvero di salita alll'importante colle del Gran San Bernardo). Forse proprio per la sua particolare posizione all'interno dell'area funeraria, la chiesa veniva indicata nei documenti medievali con il titolo di "basilica".
Sulle strutture murarie di una precedente chiesa risalente al XV secolo, è stato edificato negli anni 1728-1729 l’edificio attuale. Al termine dei lavori, tra cui la sopraelevazione del campanile, è iniziata la campagna decorativa della facciata conclusasi nel 1735.
Lo spazio interno della chiesa è dominato dall'imponente altare maggiore barocco, consacrato il 18 maggio 1670, e recante al centro una pala dipinta con il Martirio di santo Stefano.
Gli stalli del coro del XVIII secolo, in legno di noce intagliato, provengono dalla chiesa dell'antico convento di San Francesco dei Minori Conventuali, che sorgeva sino al 1836 sul sito dell'attuale piazza Chanoux (piazza del Municipio). Gli affreschi del coro sono opera del pittore Giovanni Stornone (1915). Tra gli altari laterali, risalenti al XVIII secolo ma in parte rimaneggiati nel secolo successivo, merita menzionare quello dei Santi Antonio abate e Sebastiano, su cui trovano posto due statue di san Luigi Gonzaga e di san Stanislao Kotska, e quello di san Giuseppe, decorato con una tela del 1710 rappresentante la morte del santo, e con statue di san Pietro e santa Maria Maddalena. A sinistra vicino all'ingresso, il fonte battesimale di gusto neoclassico risale al 1817.