Torre Paola fu eretta nel 1563 per volontà di Papa Pio IV (1559-1565) ad opera dei Caetani, signori di Sermoneta e San Felice per contrastare le continue incursioni dei pirati saraceni, completando un sistema difensivo che comprendeva, verso Roma, Torre Astura, Tor Caldara, Tor San Lorenzo. La torre è raggiungibile attraverso la via Torre Paola. I tempi per raggiungere la Torre Paola si aggirano intorno ai 15 minuti, prendendo come punto di origine il centro storico.

La Torre Paola è l'unica a conservare la struttura originaria. Insieme a Torre Fico fu la prima ad essere edificata, posta in un punto strategico del Promontorio a custodia della cala e la foce del canale emissario del Lago di Paola.
Particolare della Torre è la piazza d'armi a forma di scudo dopo l'attacco a sorpresa dei pirati saraceni all'inizio della costruzione dall'alto del monte.
La torre fu ultimata, fra varie difficoltà incluse le incursioni dei pirati saraceni nel 1563.

La relazione del 1614 del responsabile Grillo G.C. descrive così la torre: "La Torre Paola è posta alla radice del Monte Cercello verso Ponente, scopre tutta la spiaggia di Caprolace, Fogliano, Foce Verde, Asturi sino al Capo d'Anzi […] è Torre di grandissima considerazione e del continuo vi stanno delli vascelli assai e particolarmente l'estate tutti li vascelli che vengono dalla parte del levante la sera se fermano sotto detta torre per haver fondo capace di qualsivoglia galera o altro vascello et per assicurarsi dalli corsari […] È jurisdizione delli Signori Gaetani. Vi sta il suo custode con tre soldati. È la migliore torre della spiaggia per il concorso delli passeggieri, che il custode può guadagnare assai per l'alloggi che in essa si fa, dotata di tutte le comodità necessari […]".

Il nome Torre Paola sembrerebbe derivato dall'antica Chiesetta di San Paolo là esistente.