Già nei primi decenni del XIII secolo i documenti riferiscono della presenza di una Porta San Polo o San Paolo, per la vicinanza dell'omonima chiesa lungo l'attuale Corso Porta Reno. Rifatta nel 1426, l'odierna struttura venne costruita nel 1612 su disegno dell'architetto Giovanni Battista Aleotti (1546-1636), detto l'Argenta, che la progettò in onore del papa regnante Paolo V Borghese (da cui derivò la denominazione Porta Paola).

È indubbiamente il varco monumentale più prestigioso della città, specie sul piano del linguaggio architettonico tardo manierista e proto-barocco, come dimostra l'impaginato della facciata meridionale, realizzata in pietra marmorea con bugnati rustici coronati da un timpano curvilineo spezzato al centro per far spazio all'epigrafe encomiastica voluta dal cardinale Orazio Spinola, Legato di Ferrara per conto del papa:

Paulo. V. Pont. Max

Horatius S. E. R. Presb. Card. Spinula

Ferrariae Legatus

Portam Paulam a fundamentis

Restituit

Anno sal. MDCXII

Nel luglio 1798 i Francesi cambiarono il nome della Porta in Porta Reno, giacché a circa dodici chilometri di distanza scorreva l'omonimo fiume, mentre la struttura continuava ad assolvere funzioni militari, oltre che daziarie; nel secolo successivo l'edificio divenne una delle più importanti “ricevitorie daziarie” della città, dotata di pesa pubblica, con guardie e un portiere, il quale assieme alla famiglia usufruiva di alcune stanze al piano superiore, considerate nel 1888 inabitabili per via del pessimo stato manutentivo (Scafuri, 2003, p. 62).

I prospetti est e ovest vennero ricostruiti ex novo alla fine del XIX secolo, mentre il fronte nord, affacciato sulla Piazza Travaglio, venne parzialmente modificato con l'inserimento di marmi d'Istria in sostituzione della facciata realizzata nella prima metà dello stesso secolo in marmo di Verona.

Affiancata dai baluardi di San Paolo e San Lorenzo completati nel '600, la Porta era ulteriormente protetta da un antistante rivellino a freccia demolito nel corso dell'Ottocento, mentre i due varchi laterali risalgono al 1901. In base alle ricerche di Francesco Scafuri, sappiamo che per oltre quarant'anni non si segnalano interventi di rilievo nel manufatto,

dove continuano a svolgersi le operazioni di controllo daziario, tanto che alcuni ambienti del piano terra verso via Bologna furono utilizzati persino per pesare le carni. Questi ultimi locali nel 1947 verranno provvisoriamente concessi in affitto alla Cassa di Risparmio di Ferrara per un anno (contratto poi prorogato per un altro breve periodo), mentre le stanze adiacenti continueranno ad ospitare gli impiegati del dazio: tutto ciò comportò una serie di opere preliminari per rendere possibile la coabitazione dei diversi uffici, i cui costi andarono a carico della banca. A tal proposito, dalla documentazione del 1947 si evince che in quel periodo si eseguirono diversi lavori, che conferirono in gran parte l'assetto attuale agli interni della storica Porta.

L'edificio, dopo il breve periodo di insediamento della Cassa di Risparmio, fu destinato interamente ad accogliere gli “uffici del dazio e consumo” e ciò comportò altre modifiche interne, di minore entità rispetto alle precedenti. Al piano terra, dove in un piccolo ambiente adiacente al portale aleottiano venne ricavato il vano caldaia, si trovavano gli “uffici della pesa”, invece al primo piano quelli “ispettivi e di controllo”: tali funzioni pubbliche sono state soppresse soltanto il 31 dicembre 1972, ma i locali della porta sono stati occupati fino al dicembre 1974 da alcuni funzionari comunali. Dopo aver accolto per qualche anno gli uffici, della Divisione Imposte e Tasse del Comune di Ferrara, ora alcuni ambienti di Porta Paola sono destinati a deposito comunale dell'Ufficio Tributi, mentre diversi locali risultano inutilizzati (Scafuri 2003, pp. 63-64).

Nell'estate del 2001 l'intera facciata principale verso via Bologna è stata interessata dai lavori di restauro, diretti dal Servizio Beni Monumentali del Comune. L'ente ha inoltre promosso, con il supporto scientifico della Soprintendenza Archeologica dell'Emilia Romagna, importanti lavori di riqualificazione dell'area antistante alla Porta (2003-2004) e di scavi di tipo archeologico che hanno fatto emergere l'antico basamento:  profondo circa due metri, lo scavo è stato delimitato da una muratura di contenimento, mentre sul suo lato sud sono state costruite due gradinate rivestite di lastre e blocchi di porfido, che permettono al visitatore di scendere ad una quota di circa 80 cm rispetto al piano di calpestio della piazza, consentendo una suggestiva visione della Porta dal basso. Lateralmente, sul bordo superiore dello scavo, è stata realizzata una ringhiera metallica di protezione, mentre una passerella appositamente studiata collega la piazzetta antistante e la Porta stessa (Scafuri in sitografia).

Lo storico fabbricato è stato ulteriormente consolidato dopo il sisma del 2012 e convertito a funzione museale quale sede del Centro di Documentazione delle Mura, ossia la sede ideale ove radunare, conservare, valorizzare e catalogare anche su supporto digitale tutta la documentazione (cartacea e fotografica) prodotta dai primi anni Ottanta ad oggi, relativa al “progetto complessivo di recupero e valorizzazione dell’intera Cerchia Muraria”, il materiale presente negli archivi del Comune, nella Biblioteca Ariostea e presso lo studio dell'architetto Michele Pastore, all'epoca progettista e direttore dei lavori.

All'inizio del XX secolo si chiamava ancora Piazza di Porta Reno, ma come asserisce Gerolamo Melchiorri,

anticamente e popolarmente ancora fu denominata “Piazza del Travaglio” o del dolore, perchè fino dal 1468 alla riva del Po, presso la porta di S. Paolo, si esponevano i rei alla berlina, o alla gogna, pena umiliante, che rimonta ai più remoti tempi, abbandonata dai popoli civili. Il condannato era esposto al pubblico sopra un palco, colla indicazione del delitto e della pena a cui era stato condannato. La pena di morte invece si esercitava in antico fuori della città; e nel 1490, in un prato del Borgo di S. Giacomo, si innalzavano le forche, si decapitavano i furfanti e si impiccavano i ladri. […] Sulla Piazza del Travaglio, nei secoli XVII e XVIII si amputavano ancora le teste dei malfattori. E le ultime esecuzioni capitali ebbero luogo l'11 dicembre 1857 nella persona di Giovanni Ferrari, di anni 31, per aver ucciso l'ottuagenario suo padrone, dott. Alfonso Gandini; e il 28 settembre 1861, nella persona di Vincenzo Romoli di San Nicolò d'Argenta, uccisore di certo Galamini di Russi.