Secondo Paolo Diacono, autore nell’VIII secolo della Historia Langobardorum, a Teodolinda si deve la fondazione della chiesa, ad una data che dovrebbe situarsi intorno al 595-600.
A questo proposito, la leggenda trasmessa dal cronista trecentesco Bonincontro Morigia avvolge in un’aura miracolosa l’iniziativa della Regina: fermatasi a riposare mentre partecipava a una battuta di caccia sulle rive del Lambro, Teodolinda avrebbe avuto la visione della colomba dello Spirito Santo, che le avrebbe sussurrato la parola “Modo” (“qui”), cui la Regina avrebbe risposto esclamando “Etiam” (“si”).
Proprio in quel punto ella avrebbe allora costruito un palazzo e un oraculum, cioè una cappella dedicata a san Giovanni Battista, incunabolo della successiva basilica, mentre dalla fusione delle due parole pronunciate sarebbe scaturito il toponimo Modoetia, l’antico nome di Monza.
Adibita a cappella palatina e destinata ad accogliere le spoglie di re Agilulfo, del figlio Adaloaldo e della stessa Teodolinda, la chiesa attraversò alterne vicende nel corso del Medioevo: decaduta alla fine del regno longobardo, tornò a fiorire in età carolingia – grazie soprattutto alla protezione dell’imperatore Berengario, che all’inizio del X secolo le donò preziose suppellettili, ampliando la già ricca dotazione del Tesoro istituito da Agilulfo e Teodolinda – e accrebbe poi le sue proprietà, fino ad ottenere il dominio sul borgo, che esercitò tra il X e il XII secolo con l’appoggio sia degli imperatori di Germania, interessati a farne un centro del loro potere in Italia, sia dei pontefici, che le concessero l’autonomia da Milano.
