All'indomani della devastante eruzione del Monte Nuovo, il Viceré di Napoli Don Pedro de Toledo decise, senza alcuna esitazione, che la città di Pozzuoli doveva essere ricostruita. Le motivazioni del Toledo circa la ricostruzione della città, erano di ordine sia politico che sentimentale. Nell'economia del Vicereame Pozzuoli rivestiva un ruolo fondamentale per l'attività portuale e anche nelle strategie militari, poichè costituiva un baluardo difensivo da nord-ovest per Napoli. Don Pedro era, inoltre, legatissimo alla città flegrea, dove veniva a trascorrere i suoi momenti di svago, andando a caccia nel cratere di Campiglione, ma ne apprezzava anche la storia, la natura, il clima, ed era solito curarsi i suoi malanni con le acque termali puteolane. Il suo primo impegno fu quello di far ritornare gli abitanti che, atterriti dai continui terremoti precedenti l'eruzione, si erano rifugiati a Napoli e nei paesi vicini, e perciò decretò l'esenzione, per molti anni, dal pagamento delle imposte per tutta la popolazione. Successivamente diede l'avvio alla ricostruzione delle case, delle strade, alla riattivazione dell'acquedotto ed anche all'abbellimento della città con giardini e fontane.

Le mura del Rione Terra furono riparate e rinforzate ampliando il torrione ai piedi della rocca, e venne aperta una nuova strada per collegare Pozzuoli con Baia, dal momento che quella precedente era stata distrutta dall'eruzione e, volle anche rendere nuovamente funzionanti i bagni termali. A proprie spese fece eseguire i lavori di restauro delle chiese di San Francesco (oggi Sant'Antonio) e di San Giacomo apostolo (oggi chiesa del Carmine). Per far capire, infine, che la città era di nuovo sicura e vivibile e per dare un segnale forte della rinascita di Pozzuoli, Don Pedro fece costruire una dimora per se stesso. L'area su cui venne edificata gravita sul pendio che dalla parte alta della città, dove sorgono l'anfiteatro e altri grandiosi monumenti romani, degrada verso la zona portuale. Dalla lettura delle iscrizioni della base di una statua di Mavortio, un personaggio autorevole dell'antica Puteoli, apprendiamo che questa parte della città costituiva la Regio clivi vitrari sive vici turari, cioè il quartiere dove si concentrarono le fabbriche del vetro e dei profumi.
L'edificio, la cui costruzione avvenne quasi certamente tra il 1539 e il 1541, sorgeva, inoltre, sulla stessa area dove secondo le fonti esisteva già una residenza appartenuta ai sovrani Angioini prima ed Aragonesi poi, affiancata da un monastero benedettino che per questo motivo è indicato nelle cronache come Sant'Andrea de palatio.

l palazzo Toledo era un grosso complesso edilizio costituito, dalla dimora del Viceré, da una torre di avvistamento, e dalla cavallerizza, un edificio basso e lungo, parallelo all'attuale via Pergolesi, che ospitava gli alloggiamenti per i soldati e le stalle, e sul cui portale d'ingresso è ancora visibile lo stemma del Viceré. La torre aveva il compito di difendere il palazzo, ma anche di controllare l'ingresso del porto, ed era parte di un sistema difensivo, che faceva capo al castello di Baia, per l'avvistamento delle navi dei pirati saraceni.
Tutto il complesso venne edificato in una posizione estremamente panoramica, di fronte al golfo e al porto, ed era circondato da un rigoglioso e vasto giardino che, dall'osservazione dell'iconografia antica, appare evidente si estendesse dall'ingresso del palazzo in direzione nord, cioè verso l'attuale via Follieri e le ex Terme Lopez.
La dimora era costituita da numerose stanze, tutte magnificamente arredate, addobbate con arazzi ed affrescate, pare, dall'artista aretino Giorgio Vasari, e abbellita con numerose decorazioni marmoree, colonne e statue di epoca romana rinvenute sul posto nel corso dei lavori di costruzione del palazzo.
Il complesso edilizio, finanziato dallo stesso Don Pedro fu, con tutta probabilità, progettato da Ferrante Manlio (conosciuto anche come Ferdinando Maglione), regio architetto che godeva della fiducia del Toledo anche per i problemi di urbanistica della capitale.
Don Pedro, per molti mesi all'anno, soggiornava nel suo palazzo puteolano, non solo per i suoi momenti di riposo, di svago o per motivi di salute, ma anche per attendere ai suoi uffici politici e amministrativi di Viceré, com'è dimostrato dai numerosi documenti firmati e datati da Pozzuoli recanti la dicitura Datum Putheolis o Civitate Putheolis.
Dopo la morte del Vicerè il palazzo, almeno per tutto il Seicento è appartenuto alla famiglia Toledo ed ha continuato ad avere la magnificenza di un tempo. Quando i Toledo lasciarono Pozzuoli per tornare in Spagna, la dimora del Vicerè conosce un primo momento di abbandono fino al 1872 quando, su progetto dell'arch. Ernesto Villari, vennero aggiunti altri due piani diventando l'ospedale di Pozzuoli, funzione che mantenne fino al 1970 quando venne sgomberato in conseguenza del bradisisma. Per un breve periodo ospita la Biblioteca Civica ma, viene definitivamente abbandonato dopo il bradisisma degli anni 1983-1985. Nel 2005 il Comune di Pozzuoli ottiene un finanziamento europeo per un progetto che destinava Palazzo Toledo a Biblioteca e Archivio Storico.
In questa nuova veste la dimora di Don Pedro de Toledo, viene riaperta al pubblico nel marzo del 2009 e dall'aprile 2011 ospita l'Archivio Storico, la Biblioteca Civica e l'Ufficio Beni Culturali, diventando così il Polo Culturale del Comune di Pozzuoli.
La ristrutturazione e la restituzione di Palazzo Toledo alla cittadinanza puteolana, è un giusto riconoscimento all'opera svolta dal Viceré in favore della città. Pozzuoli e i Puteolani devono, infatti, tantissmo a Don Pedro de Toledo in quanto non è azzardato affermare che senza il suo intervento oggi, forse, Pozzuoli non esisterebbe.