La chiesa di San Salvatore aveva una forma rettangolare ed il suo interno era diviso in tre navate che si concludevano in un'abside. Gli interni della chiesa di San Salvatore erano affrescati da un pittore di epoca ottoniana e la copertura superiore dell'edificio era a capriate in legno. Della decorazione ci giunge soltanto la parte centrale della pala realizzata da Giampietrino raffigurante la Madonna con Bambino, conservata nella cappella centrale di sinistra dell'attuale basilica.
L'antica chiesa a causa delle infiltrazioni d'acqua dell'Olona e dei movimenti sismici dell'epoca, nei primi anni del '500, crollò irrimediabilmente.
I capi delle nobili casate del borgo di Legnano, quali i Lampungnani e i Vismara, decisero di costruire una nuova chiesa affidando la progettazione a Bramante.
La chiesa venne edificata tra il 1504 e il 1513. A realizzare la chiesa provvide un capomastro anonimo affiancato al più grande artista della zona, il giovane pittore Gian Giacomo Lampugnani. Egli dovette trasporre in muri i disegni e le indicazioni del Bramante. Questi preziosi progetti sono però oggi scomparsi.
Dell'antica chiesa venne mantenuto, dopo lavori di consolidamento, il campanile del quale si possono vedere i resti nell'attuale base della torre campanaria, realizzata nel 1752. L'orientamento iniziale della chiesa era diverso dall'attuale infatti il portale di ingresso era sul lato nord (di fronte all'attuale palazzo del Municipio) e fu spostato dal Richini sul lato ovest (dove è tutt'ora) nel 1810.
L'edificio presenta una forma della pianta a croce quadrata, divisa nel centro ad ottagono e con le due cappelle simmetriche ai lati dell'altare maggiore. Essi sono caratteristici elementi dell'epoca del Bramante che ebbe molti imitatori tra i suoi contemporanei.
Nel 1513 i lavori si arrestarono per motivazioni economiche legate alla perdita di potere delle casate nobiliari a causa dell'avvento delle dominazioni francese, spagnola e austriaca e l'esterno della basilica rimase per molti anni rustico in mattoni. La basilica rimase quindi priva del suo aspetto esterno. Al contrario si può affermare che nel suo aspetto interno è distinguibile per una grande ricchezza.
Attribuibile o no a Bramante, la basilica di San Magno infatti resta un monumento di grande valore artistico anche per i dipinti che ospita al suo interno, tra cui la grande pala dell'altare maggiore di Bernardino Luini (1523), gli affreschi di Bernardino Lanino (1560), le decorazioni della volta e dei pilastri della cappella dell'Assunta dei pittori legnanesi Francesco e Gianbattista Lampugnani (1633).
Durante la sua storia, la basilica di San Magno non subì modifiche sostanziali. Nel 1840 fu realizzata l'attuale porta principale e venne demolita la casa del sacrestano, che era situata verso l'attuale municipio. Nel 1888 fu realizzato il primo restauro, seguito dal successivo che durò dal 1911 al 1914 e reso necessario dai danni riportati dall'edificio in seguito al ciclone che colpì Legnano nel 1910. In questa occasione fu allungato l'atrio principale, vennero rifatti l'atrio e la facciata e furono realizzati i timpani sulle porte. Nel 1909 fu invece eretta la nuova sacrestia. Da ultimo la basilica fu restaurata nuovamente dal 1963 al 1964.