Del periodo altomedioevale non ci sono documenti ma sembra che la città, con la formazione dello stato dei papi, sia stata sempre strettamente dipendente da Roma. Sembra anche che abbia svolto una funzione agricola, con la fondazione di una curtis agricola. Dalla documentazione  medioevale, Frosinone appare un piccolo castello, ma una carta del 1081 la denomina civitas, riconoscendole un ruolo più rilevante. Si ritiene comunemente che Frosinone abbia avuto un ruolo essenzialmente militare per via della rocca eretta nel punto di congiunzione di diverse strade. Da questa fortificazione vennero fronteggiati i turbolenti signori de Ceccano. Nel secolo XI il risveglio economico determinò la nascita e l’evoluzione di nuovi gruppi. Anch’essi assunsero un ruolo militare sostituendosi ai milites, che, dal secolo precedente, avevano costituito una “consorteria” per governare la cittadina: tale istituzione non decadde e venne riconosciuta e approvata anche dalla Chiesa romana.

Il regime condomimale fu confermato da Innocenzo III nel 1207, per mezzo di una concessione della durata di tre generazioni, ma il controllo di Frosinone venne insidiato dagli anagnini Mattia, Adinolfo Nicola per tutta la seconda metà del Duecento. Soprattutto Adinolfo fu reponsabile di violenze e devastazioni contro il castello e i suoi abitanti. Frosinone i schierò con i pontefici, e il costante appoggio papale rese vana l’azione dei nobili di Anagni. La fedeltà alla Chiesa condusse molti frusinati ad assumere importanti uffici nella curia papale; alcuni divennero prelati e legati. La prevalente funzione militare di Frosinone nel corso del Medioevo è documentata dalle fonti conservate negli archivi pontifici: in un registro in cui sono elencate le spese sostenute per la riparazione della rocca. Il papato fu interessato a tali lavori sia per la funzione militare assolta dalla fortificazione, sia perché la costruzione era sede della curia rettorale di Marittima e Campagna, sia, infine, per consolidare il proprio predominio nel comune frusinate. Il documento è interessante perché apre uno spiraglio su diversi aspetti della vita economica, sociale e sulle tecniche edilizie locali. Il castello possedeva, oltre alla cinta muraria, almeno due torri, locali per la residenza del rettore, una loggia, e diversi ambienti per la guarnigione. Sin dal XIII secolo Frosinone fu sede ordinaria del rettore di Campagna e Marittima, la provincia pontificia del Lazio meridionale, anche se sovente l’alto prelato abitò in altre città come Ferentino, Anagni e Priverno.

Alla fine del Quattrocento l’antico abitato di Selva Molle o Selva dei Muli venne associato al comune di Frosinone. Il castello sorgeva sopra un modesto cono vulcanico nelle vicinanze del fiume Sacco a qualche chilometro da Frosinone verso Patrica e Supino. Si notano ancora mura medioevali di cinta, a fortificare la sommità del colle, luogo dal quale era agevole controllare la strada verso la Marittima e la rete viaria territoriale. Decaduto attorno alla metà del Quattrocento, in poco tempo il castello venne trasformato in casale, e venduto ai certosini di Trisulti che lo adibirono a grancia monastica, cioè a semplice azienda agricola: il territorio era ricco di sorgenti d'acqua. I certosini trasformarono il villaggio, e il palazzo pontificio fu ingrandito. Agli inizi del XIV secolo il castello frusinate strinse un'alleanza con il potente comune di Alatri. Con questo patto Frosinone si impegnava a intervenire con propri rappresentanti al parlamento alatrino e a partecipare anche alle spedizioni belliche dell’alleato, conservando però le proprie insegne militari.

La città è ricordata alla fine del Quattrocento dall’umanista Giovanni Antonio Sulpicio che la menziona nel suo “Campaniae fletus” con parole elogiative. Dello stesso tenore è l’elogio elevato alla cittadina dall’altro umanista cinquecentesco Francesco Franchini: “... mi avvincono i colli dell’ameno Frosinone! ed i campi dolci e le acque...”. Nel Cinquecento la città fu coinvolta in due guerre. Nel 1526 la guarnigione pontificia riuscì a contrastare validamente le truppe spagnole che la assediavano ma l’anno dopo Frosinone fu saccheggiata da truppe francesi e fiorentine dopo essere stata contagiata dalla peste portata dai lanzichenecchi. Dopo questi fatti, connessi col sacco di Roma, la rocca di Frosinone, quasi del tutto distrutta, venne ricostruìta ai tempi del cardinale Cicada. Probabilmente fu spostata di sito e occupò il posto in cui oggi sorge il palazzo del governo. La rocca venne costruita secondo i dettami cinquecenteschi e il portale principale, secondo taluni, fu disegnato da Michelangelo. Qualche anno dopo Frosinone fu occupata dagli spagnoli che marciavano verso Roma contro Paolo IV. I danni furono ingenti: molte chiese furono ridotte in macerie. Per un periodo molto lungo la città fu impegnata nella ricostruzione e, per pagare i debiti, il comune fu costretto ad alienare diversi beni fondiari. Nella seconda metà del Cinquecento, con la riorganizzazione dello stato, la residenza dei governatori pontifici venne fissata definitivamente a Frosinone. Nuove funzioni furono da loro assunte: il controllo dei comuni, il comando della polizia statale (i birri furono impegnati a combattere contro un brigantaggio molto attivo organizzato in bande armatissime), l’istituzione di un tribunale d’appello in luogo delle corti signorili. L’ufficio del governatore, inoltre, estese il suo raggio d’azione e aumentò il proprio personale.