L’edificio fu eretto e in buona parte decorato nel 1506, come appare dalle lettere di Arcari che forniscono informazioni sulle quattro camere a volta del piano terreno, caratterizzate dalla presenza di imprese: “la camera del sole”, “la camera del crogiolo”, “la camera con l’arma del re di Francia” (porcospino), e “la camera con l’arma dell’Imperatore”. Nell’ottobre del 1506 fu realizzata la “loza”, il grande porticato a sette archi che caratterizza il fabbricato sulla fronte nord. Nel novembre dello stesso anno fu completata la sala del primo piano, quella destinata ai “trionfi”, con un soffitto a cassettoni decorati con l’impresa del “crogiolo”. Lo splendido soffitto, trasportato a Palazzo Ducale nel 1601, orna ancor oggi due ambienti dell’appartamento di Vincenzo nella reggia gonzaghesca. L’emblema prediletto di Francesco II, che si ripete nei lacunari, e i fregi dorati sono di mano di Lorenzo Leonbruno, autore di molti altri interventi pittorici e ornamentali nel Palazzo di San Sebastiano. Infatti, sempre a Leonbruno fu affidata la decorazione della loggia (tracce di affresco vi comparivano ancora agli inizi del Novecento) e delle pareti esterne, della quale restano pochi brani di fregio sul lato sud e in una porzione di intonaco, con riquadri a finti marmi rossi e bianchi divisi da fascette verdi, sull’angolo sud-est.
Nel 1507 il palazzo risulta già terminato nel corpo longitudinale (54 x 8 m) secondo lo schema ancora oggi leggibile: la loggia al centro con due ambienti in serie a ogni estremità e, al piano superiore, la grande “sala dei trionfi” con un ambiente sulla testata ovest e due su quella est.
Il corpo aggettante verso sud, che contiene le due camere a volta del piano superiore, è con ogni probabilità il risultato di un ampliamento avvenuto pochi anni dopo, quando fu realizzata, per opera di Alessio Beccaguto, una nuova cinta bastionata in sostituzione delle precedenti mura trecentesche.
Il nuovo corpo riprodusse i caratteri architettonici esterni di quello precedente (cornicione e decorazioni) occultando il cornicione originario ancor oggi visibile, con la sua vivace decorazione, nel sottotetto sovrastante le camere delle “frecce” e delle “briglie”.
Il palazzo, che rimase proprietà gonzaghesca fino al XVII secolo, fu concesso in uso a illustri personaggi come il marchese Maffei o a esponenti dei rami laterali della famiglia.
Nel XVIII secolo l’edificio è indicato nei documenti come “Palazzo delle Bugandere”, perché le lavandaie stendevano sotto il porticato i panni lavati nella contigua Fossa Magistrale. Nel 1756 fu adibito a caserma e nel 1786 l’architetto Paolo Pozzo lo inserì in un ampio progetto di adattamento a ospedale. Lo stesso Paolo Pozzo suggerì successivamente l’utilizzo a carcere. Risale al 1883 l’adattamento a lazzaretto, che ha causato le maggiori trasformazioni nell’edificio (sopraelevazione e nuova scala) e la quasi totale perdita delle decorazioni murali. Altre modifiche avvennero nel corso del Novecento, quando il palazzo divenne sede di bagni pubblici, di scuole, di depositi e circoli ricreativi.
Il ripristino iniziò nel 1995 con l’obiettivo di recuperare per quanto possibile l’aspetto originario dell’edificio e recuperare le sue antiche decorazioni. La campagna di restauro si concluse nel 2003 riproponendo alla vista del pubblico la “Loggia dei marmi” e buona parte dei cicli di affreschi rinascimentali che ornavano le volte dei soffitti e le pareti.
Il Palazzo di San Sebastiano è divenuto dal 2005 sede del Museo della Città. Al suo interno storia e arte guidano il visitatore all’interno di un suggestivo percorso che, attraverso un importante gruppo di opere, racconta i momenti più emblematici della storia di Mantova e ne rappresenta la grande civiltà artistica.