Il periodo di storia del Circeo tra il IV secolo e l'XI secolo risulta di grande oscurità. Si può supporre che il centro condivise le vicende che interessarono il resto del Lazio, ma solo lo sviluppo degli scavi permetterà forse di restituire i frammenti di questa storia perduta. Probabilmente un duro colpo agli insediamenti dell'area venne dalle scorrerie dei pirati saraceni, a cui Papa Giovanni VIII si oppose nel 877, insieme alle repubbliche marinare di Gaeta, Napoli e Amalfi.
Per avere altre informazioni sull'antica Circeii dobbiamo aspettare il XII secolo, quando ormai il nome in uso è quello di Rocca Circea. Resta ignota la data della prima costruzione della fortezza e chi ne fu l'autore, se il Pontefice o gli abitanti di Terracina, ai quali però papa Gelasio II volle che fosse affidata, tra il 1118 e il 1119.
Questa delega terracinese ebbe breve durata, infatti dopo poco l'amministrazione della Rocca passò a Marino di Formosa e ai suoi figli in circostanze per noi ignote. Si può ipotizzare che Marino, con famiglia originaria di Terracina, fosse un capitano inviato sul luogo che, con un colpo di mano, si impadronì del territorio assegnatogli. In questa direzione andrebbe l'accordo del 1132 con Gaeta: tale patto, molto simile a un'investitura feudale, avrebbe potuto proteggere l'usurpatore da una rappresaglia di Terracina, all'epoca nemica di Gaeta.
Ma anche questo nuovo assestamento si rivelò effimero, in quanto nel 1138 Gaeta entrò a far parte del Regno Normanno. E ancora una volta è difficile sapere cosa toccò in sorte al Circeo.
All'inizio del XIII secolo scoppiò la rivolta di Terracina contro i Frangipane, i quali si videro strappare nel 1202 la Rocca Traversa e nel 1203 la Rocca Circea. Immediato fu l'intervento di Papa Innocenzo III, che ordinò la restituzione dei feudi. Ignoriamo l'esito dell'intervento del Papa, tuttavia nel 1207 Terracina tornò a controllare la Rocca Circea, pur sotto la supervisione dei Frangipane.
Nel 1212 iniziò il periodo di insediamento dei Templari, che con molte difficoltà subentrarono ai monaci di Grottaferrata presso la chiesa di S. Maria della Sorresca. Probabilmente Innocenzo III volle garantirsi, dopo le vicende degli anni precedenti, un controllo più diretto su una postazione di alto valore strategico.
La scelta di presidio fu confermata anche da Papa Gregorio IX, che nel 1239 ordinò ai terracinesi di realizzare, a spese della Camera, fortificazioni presso il Circeo. Nel 1259 iniziò il dominio dei Pironti, che durò fino alla fine del secolo. Nel corso di questo periodo gli abitanti della Rocca Circea divennero a pieno titolo cittadini di Terracina.
