La storia dell'isola di Procida è antica quanto i tempi. Delle tre maggiori isole del golfo di Napoli, Procida è la più piccola ma fu tra le prime ad essere abitata.
Tra il XVII e XVI secolo a.C., i Micenei la prescelsero come sede per la fabbricazione dei metalli e la testimonianza della loro presenza è rappresentata dai numerosi reperti ritrovati sull'isolotto di Vivara.
Tra l'VIII VII secolo a.C., probabilmente risiedettero i Cumani ai quali, secoli dopo, seguirono i Romani.
Nel VI secolo d.C. Procida fu annessa al territorio di Napoli sotto la giurisdizione del Conte di Miseno. Procida subì numerose scorribande saracene: i Visigoti di Alarico, i Vandali di Genserico funestarano le coste campane. Gli abitanti della vicina Miseno furono allora costretti a rifugiarsi a Procida e il conte annise quel territorio tutto alla giurisdizione dell'isola tanto che ne derivò il nome Monte di Procida.

Intorno al X secolo, si contano sull'isola i primi insediamenti benedettini che si stabilirono, dapprima, nel cenobio di Santa Margherita Vecchia a Marina Chiaiolella. A seguito delle continue incursioni saracene, andò consolidandosi il borgo di Terra Murata, allora denominato Terra Casata: intorno al XI secolo, ivi, venne costruita dai padri benedettini l'Abbazia di San Michele Arcangelo.
Nel XII secolo Procida divenne feudo dei Normanni insieme a Monte di Procida. Feudatari dell'isola furono i "da Procida" con il famoso Giovanni da Procida, eroe dei vespri siciliani, primo e grande signore dell'isola. Molto probabilmente a Terra Murata è da ricercarsi la residenza della famiglia da Procida.
Nel 1340 Procida, Monte di Procida e la piccola Vivara furono acquistate dalla famiglia Cossa alla quale, nel secolo successivo, segui la dinastia degli Aragonesi.

Nel 1529 il re Carlo V d'Asburgo affidò Procida ai d'Avalos. Personaggio di spicco fu Innico d'Avalos che apportò notevoli cambiamenti sull'isola e, in particolare, al borgo abitato di Terra Casata per meglio proteggere gli abitanti dalle frequenti incursioni saracene.
Di sua opera furono l'edificazione del Castello d'Avalos e la cinta muraria (accessibile solo attraverso il portale di Ferro ancora visibile e situato presso il belvedere dei due cannoni) che fece denominare, da allora, il borgo di Terra Casata, in borgo di Terra Murata (terra cinta di mura).
Alla famiglia d'Avalos, a seguito di una confisca, nel XVIII secolo seguirono i Borbone.
Procida e la sua storia si fusero, da allora, con la storia del regno di Napoli.
L'isola divenne feudo di caccia "riserva di caccia imperiale" e il castello d'Avalos, dapprima fu trasformato in palazzo reale e successivamente in Bagno Penale.