La prima pietra della chiesa fu posta il 17 aprile 1565 da Cosimo I de' Medici, il committente del rinnovato spazio pubblico di piazza dei Cavalieri per l'Ordine dei cavalieri di Santo Stefano, fondato dal granduca per combattere la pirateria turca nel Mediterraneo.

Progettata da Giorgio Vasari, per costruirla in piena libertà venne demolita una vecchia chiesa di San Sebastiano alle Fabbriche Maggiori, citata dal 1074, che prendeva il nome dalle officine dei fabbri presenti nella zona, almeno dal VII al XIII secolo. Ai lavori sovrintese David Fortini e furono ultimati nell'agosto del 1567; il 21 dicembre 1569 la chiesa venne consacrata.

Il campanile venne aggiunto tra il 1570 e il 1572: caratterizzato da un'elegante cella campanaria con trifore, fu eretto da Giovanni Fancelli su disegno del Vasari. Nel secolo successivo fu decorata con la maggior parte delle tele che ancora vi sono esposte, dipinte dai maggiori maestri del Seicento fiorentino. L'altare e la navata furono progettati da Pier Francesco Silvani.

Tra il 1683 e il 1691 furono edificati i due corpi laterali, usati come spogliatoi e magazzini dei cavalieri. Nel Settecento alcuni progetti (di Gherardo Mechini, Paolo Guidotti...) suggerirono di trasformare la pianta della chiesa a croce latina, ma non vennero messi in opera.

Nell'Ottocento di nuovo fu indetto un concorso per rinnovare drasticamente il volto della chiesa: dei numerosi progetti pervenuti (di Ranieri Gherardi, Torpè Donati, Alessandro Gherardesca, Florido Galli, Niccolò Matas e Pasquale Poccianti) venne scelto quello del Poccianti, che prevedeva la realizzazione di due navate laterali articolate per mezzo di grandi colonnati, ma nessuno venne attuato. Nel 1859 l'ingegner Gaetano Niccoli, dopo la soppressione dell'Ordine, realizzò due vani simili a navate a partire dai corpi laterali, con la sistemazione che tutt'oggi si può vedere.