Una delle prime preoccupazioni di Paolo III fu quella di rendere Perugia una città più sicura, grazie al progetto di innalzare una fortezza, dal momento che ne era totalmente sprovvista. Insieme ad Ancona, Perugia in quel periodo era uno dei luoghi più importanti per lo Stato Pontificio e nel papa era ancora vivo il bruciante ricordo del Sacco di Roma, e dell'enorme utilità di avere un rifugio sicuro come lo fu Castel Sant'Angelo all'epoca.
L'opportunità di un castello fortificato nasceva anche dall'esigenza di proteggere oltre alle coste anche l'entroterra dall'avanzata dei turchi, senza contare che sarebbe tornato buono anche in occasione delle velleità di nobili e fuoriusciti in cerca di rivincite. Questo è lo sfondo sul quale si colloca la costruzione della Rocca Paolina.
L'incarico di erigere la Rocca Paolina fu dato ad Antonio da Sangallo. L'architetto studiò con molta accortezza dove e come collocare la nuova costruzione, e dopo molti sopralluoghi, scelse di costruirla sul Colle Landone, dove sorgevano le case appartenenti alla famiglia dei Baglioni.
La posizione era strategica e dominante il centro della città, i borghi di San Pietro, di Porta Eburnea e di tutta la zona sottostante fino a Monteluce.
La nuova fortezza avrebbe avuto il compito di difendere la città nel suo lato più debole, la parte più scoperta, quella da dove, da Totila in poi, erano giunti tutti gli attacchi degli eserciti invasori. La zona opposta della città invece, quella del Bulagaio e di Porta Sant'Angelo, era praticamente inaccessibile, buona solo come via di fuga.
In quel periodo la città di Perugia era descritta come fra le più belle non solo d'Italia, ma dell'Europa intera, con le sue settanta torri, la cerchia di mura etrusche lungo l'intero perimetro, i palazzi signorili, le cattedrali, in pratica un vero e proprio gioiello. La costruzione della Rocca Paolina determinò guasti irreparabili alla morfologia cittadina, deturpando irrimediabilmente il profilo della città. Per fare posto alla fortezza fu demolito praticamente un intero quartiere, fra cui nove chiese, due monasteri, ventisei torri, oltre un centinaio di case e numerosi palazzi signorili. Venne abbattuto anche l'arco etrusco che si trovava all'altezza dell'attuale via Alessi.
La fabbrica della Rocca Paolina fu terminata nel giro di un paio d'anni, sotterrando definitivamente le mura etrusche, le case dei Baglioni, chiese, altari, al posto dei quali sorse il simbolo per eccellenza del dominio pontificio.
Con l'erezione della Rocca Paolina, la trasformazione del libero Comune di Perugia in una città dello Stato Pontificio era completata.