Nel 1540, durante il papato di Paolo III Farnese, Perugia, dopo la sconfitta nella "guerra del sale", perse da ultimo comune di Italia la sua indipendenza. In segno di affermazione del rinnovato dominio pontificio, Antonio da Sangallo il Giovane, fu incaricato di costruire un'imponente fortezza, stavolta sul colle Landone, distruggendo l'intero quartiere dei Baglioni (la famiglia perugina più in visa al Papa) e il borgo di San Giuliano. A questo scopo più di 100 case, ma anche chiese e monasteri vennero rase al suolo o per ricavarne materiale per la costruzione o utilizzate come costruzioni della Rocca.
Il Papa volle che il suo progetto venisse realizzato in tempi brevi; incaricò quale architetto dell'opera Antonio da Sangallo il Giovane, che riuscì a fare della nuova Rocca (voluta da Paolo III e perciò detta "Paolina"), non solo una possente costruzione militare, ma anche una grande opera d'arte. L'architetto ebbe l'accortezza di non distruggere Porta Marzia, di origine etrusca: la smontò e la reincastonò nella Rocca, così come oggi appare, pur privandola della sua antica funzione. Il Papa in persona effettuò in 3 anni ben 7 sopralluoghi per accertarsi che tutto procedesse nei tempi previsti. Per reperire denaro non si esitò a disfare e poi vendere singoli pezzi di travertino dell'antica porta etrusca di Porta Sole, probabilmente ubicata all'estremità nord di P.zza Matteotti, già del Sopramuro. Fu così che l'immenso edificio fu completato in soli 3 anni, impresa ancora oggi difficilmente realizzabile.La Rocca, in piena funzione già dal 1543, consisteva, come ben dimostra l'iconografia pervenutaci, in una complessa struttura articolata in diversi volumi e architetture, aventi peraltro anche funzioni diverse: in primo luogo la Fortezza, distinguibile in uno zoccolo dalla maschia struttura militare (che è poi la parte oggi più facilmente riconoscibile) destinata alle soldatesche, agli animali, alle armi e ai magazzini; quindi il sovrastante palazzo del Papa o del Castellano, ricchissimo di eleganti architetture di sale, affreschi e decori. Seguiva poi il caratteristico "Corridore", struttura alta e stretta, dotato di un percorso scoperto e di due coperti, avente la funzione di stabilire un collegamento diretto con la "Tenaglia", struttura solamente militare, protesa verso la campagna dal lato di Santa Giuliana, tradizionale punto debole delle difese perugine. La più modesta dimensione della "Tenaglia" mostra bene quanto la Rocca fosse stata concepita essenzialmente verso l'interno della città. Il punto estremo della "Tenaglia" era solo 4 metri dall'attuale statua di Garibaldi, in Largo Cacciatori delle Alpi.

L'intera Rocca era circondata da ampi fossati; solo nel 1800 fu colmato quello del fronte principale, verso l'attuale Corso Vannucci, venendosi così a realizzare la piazza intitolata al cardinale Rivarola, il Governatore pontificio che volle tale sistemazione (oggi Piazza Italia). L'occasione della Rocca Paolina è propizia anche alla riorganizzazione urbanistica dell'intero centro cittadino, finalizzata ad eliminare, almeno in parte, il dedalo di vicoli che tradizionalmente favorivano le sommosse popolari: le odierne Via Mazzini e Via Calderini, nonché lo stesso sbocco di Corso Vannucci su Piazza Italia, vengono aperte in tale occasione, anticipando di 3 secoli la soluzione di sventramento che il barone Hausmann realizzò nel 1800, nel centro di Parigi per lo stesso motivo. Ulteriori dolorose alterazioni di importanti vestigia cittadine, causate anche queste dalle esigenza balistiche della Rocca, furono la demolizione della chiesa sovrapposta di San Ercolano e forse anche della cuspide del campanile di San Domenico.
Dalla metà dunque del 1500 la Rocca ebbe a sovrastare l'intera città, segnandone l'immagine con la propria sagoma minacciosa e contrapponendosi al vecchio cuore cittadino (il Duomo, la Fontana Maggiore, il Palazzo dei Priori), che andò inevitabilmente degradandosi, come mostra l'immagine ottocentesca del maggior simbolo civile della città. Oggi, dall'esterno, rimane visibile solamente un tratto delle mura di sostegno in Viale Indipendenza e il bastione di levante sulla Via Marzia, sulla quale si apre l'etrusca Porta Marzia, dalla quale si accede alle imponenti fondazioni che utilizzarono il quartiere dei Baglioni, con la via Bagliona e sue case in pietra. Un altro percorso molto suggestivo è quello delle scale mobili che colllegano il parcheggio di Piazza Partigiani con Piazza Italia attraverso la Rocca.