Il palazzo venne costruito entro il 1769 dall’architetto Giambattista Novello per il giurista Andrea Maria Maldura, su preesistenze della famiglia Mussato. Il complesso originale insiste su un’area di quasi 7000 mq e risulta costituito da tre edifici: il palazzo principale con il corpo centrale monumentale e la lunga ala, e due fabbricati minori su via Calfura, realizzati entro il 1784, come risulta dalla pianta del Valle.
Tra gli anni Dieci e la metà dell’Ottocento si registrano consistenti interventi di riordinamento del cortile e dei locali di servizio, oltre che di una porzione di palazzo da affittarsi. Viene inoltre segnalata la presenza di una ricca biblioteca in 6 delle 14 stanze del piano nobile, «con suolo a terrazzo magnifico, soffitto alla sansovina».
Nel corso del Novecento ai tre edifici esistenti si aggiungono basse ed estese propaggini, destinate ad alloggi, servizi ed uffici per il Comando dei Carabinieri, di cui il complesso è sede dal 1927 fino al 1961. Segue uno stato di totale abbandono fino al passaggio all’Università di Padova, che nel 1970 lo acquista dagli Emo Capodilista-Maldura, ai quali è pervenuto in eredità dalla fine dell’Ottocento.
In una condizione di generale degrado, con squarci ai coperti e crolli nei soffitti sottostanti, il palazzo viene restaurato su progetto dell’ingegner Giulio Brunetta; dei due edifici minori, quasi impraticabili, viene conservato e riadattato solo quello porticato su via Calfura.
Ripetutamente restaurato nel corso degli anni Duemila a seguito di crolli e danneggiamenti legati anche a eventi sismici, nel 2019 il palazzo ha visto svuotarsi le sue sale dall'omonima Biblioteca, trasferitasi in nuova sede: gli ambienti storici sono così rimasti liberi per nuove destinazioni d’uso.
A ridosso della sua edificazione, a decorare Palazzo Maldura vennero chiamati artisti di primo piano nel panorama artistico padovano. Le sale più rappresentative furono affidate a Costantino Cedini (1741-1811), che dispiegò nello scalone, nell'antisala e nel grandioso salone da ballo una serie di soggetti allusivi alle virtù del committente. Alcuni ambienti posti sul fronte meridionale del Palazzo hanno visto all’opera Giambattista Mengardi (1738-1796), forse originariamente responsabile dell’intera sequenza di camere poste a ovest del vestibolo. L'ambiente angolare di sud ovest venne però profondamente rinnovato nel primo Ottocento e, in ragione dello stile adottato, viene oggi identificato come Sala Etrusca. A questa segue la cosiddetta Sala Ducale oggi detta Piranesiana per via delle decorazioni delle pareti, che riproducono quattro incisioni di Giambattista Piranesi tratte dalle Vedute di Roma e dalle Antichità Romane e qui amplificate su scala monumentale. Alla seconda fase decorativa appartengono anche gli affreschi dell'ala nord est, dove un ruolo di spicco ricoprì Giambattista Canal (1745-1825), intervenuto nella Sala delle Grazie – il soffitto, purtroppo perduto, è documentato oggi solo da una fotografia – e nella cosiddetta Sala Ercolanese, tinello invernale di casa Maldura.