Istoria acestei cetati incepe in 1534, cand Ridolfo Baglioni a ocupat Perugia, a ucis nuntiul papal, Cinzio Filonardi, si a ars resedinta acestuia, fostul Palazzo del Podesta. Cand fortele papale au recucerit orasul in 1535, noul nuntiu Marino Grimani, l-a exilat pe Baglioni si i-a confiscat toate proprietatile. El si-a stabilit resedinta in palatul care a apartinut familiei Baglioni, si a inceput fortificarea acestuia.

Piatra de temelie a noului palat a fost pusa in noiembrie 1540, iar Nuova Sapienza a fost demolata la scurt timp dupa aceasta, pentru a face loc noii constructii. Se pare ca Pier Luigi Farnese a proiectat complexul pentru uz propriu. Cu toate acestea, in curand, atentia i-a fost atrasa de poriecte mai interesante in Parma si Piacenza. Fiul sau, Ottavio Farnese, pe care Papa Paul al III-lea intentiona sa-l pronunte,,Capitan Perpetuu” in Perugia, a ramas in fostul palat al familiei Baglioni, in timp ce construirea noului palat continua in jurul acestuia. Fatadele de vest si de est ale palatului incorporeaza Porta Marzia ca portal central. In septembrie 1541, cand Papa Paul al III-lea a vizitat Perugia. Vazand cladirea, se pare ca acesta ar fi spus “aceasta nu este suficient; vreau sa se construiasca o cetate".

Rolul jucat de Antonio da Sangallo in proiectul revizuit este necunoscut, el nefiind mentionat in documentele de dupa 1542, atunci cand Galeazzo Alessi a ajuns in Perugia impreuna cu nuntiul papal Ascanio Parisani. Oamenii din Perugia au fost fortati sa lucreze la constructia noii cetati si sa plateasca pentru asta, cu toate ca Parisani a reusit sa convinga pe Papa Paul al III-lea sa reduca la jumatate taxele impuse in acest scop.

Odata ce structura initiala a fost finalizata, au inceput lucrarile la cladirile interne, inclusiv un palat pentru nuntiul papal. Galeazzo Alessi a finalizat aceasta faza a lucrarilor in 1547.

Cand armata lui Napoleon a invadat Italia in luna februarie 1797, perugienii s-au razvratit impotriva autoritatii papale, au eliminat inscriptiile si si insemnele papale de pe peretii Rocca si au aruncat statuia Papei Paul al III-lea in sant.

Partial distrusa in 1848, si reconstruita in 1860 de catre Papa Pius al IX-lea, cetatea a fost in cele din urma demolata in urmatoarele decenii dupa unificarea Italiei, oferind spatiu pentru construirea mai multor edificii si sistematizari, Piazza Italia, via Masi, Giardini Carducci, Viale Indipendenza. Cu astfel de planificare urbana, din antica Rocca Paolina a ramas doar subsolul Palatului Papal. Lucrarile de excavare au inceput in 1932 si au fost finalizate in 1965, fiind deschis pentru public ca,,orasul subteran”. In cele din urma, incepand cu anul 1983 Rocca Paolina este traversata de scari rulante, care duc de la statia de autobuz pana la acropola etrusca. Astazi, spatiile mari existente aici sunt utilizate pe tot parcursul anului pentru diverse evenimente culturale.