Fu costruito nel 1227, committente il bresciano Laudarengo Martinengo nominato podestà di Mantova[1]. Unitamente alla Torre del Broletto, alla quale è addossata Casa Tortelli, rappresentò il centro amministrativo del comune di Mantova. Verso piazza Broletto fu collegato al palazzo degli ex Magazzini Generali con la costruzione dell'Arengario e al palazzo della Ragione sul lato affacciato su piazza Erbe.
Sulla facciata di piazza Broletto è visibile una statua duecentesca raffigurante Virgilio in cattedra (la vècia in dialetto), con la berretta dottorale e le braccia poggiate al leggio che reca incisa l'iscrizione Virgilius Mantuanus poetarum clarissimus.
Subì rifacimenti e modifiche architettoniche anche a causa dei numerosi incendi accaduti nel corso dei secoli. Dal 1462 fu sottoposto ad un'importante ristrutturazione diretta da Giovanni Antonio da Arezzo[2] su incarico di Ludovico III Gonzaga. Dell'epoca e legata al gusto di Luca Fancelli, è la merlatura cieca posta a coronamento dell'edificio, trasformato per volere del marchese Ludovico Gonzaga.
Negli ultimi tre secoli è stato destinato a svariati usi tra cui anche quello di carcere. Secondo gli attuali progetti del Comune di Mantova, il Palazzo verrà restaurato[3] anche per ospitare la sede del Municipio, ritornando ad essere il centro amministrativo della città.
Sabato 7 dicembre 2024 ha aperto le porte ai visitatori il Museo Virgilio, uno spazio che celebra lo storico palazzo che viene restituito al pubblico, diventando un percorso spazio-temporale nell’opera e nella leggenda del grande poeta latino.