Nonostante la piccola estensione, il territorio è densamente abitato fin dal medioevo, e la popolazione di oltre 10.000 abitanti è, per densità, fra le maggiori del pianeta.
In passato fu chiamata “Prochyta” che secondo alcuni studiosi starebbe a indicare “protesa – coricata”, mentre secondo altri autori, questo nome deriva da Prima Cyme, ovvero "prossima a Cuma", come doveva apparire l'isola ai coloni greci nella migrazione dall'isola d'Ischia a Cuma.
Recenti ritrovamenti archeologici sulla vicina isola di Vivara (un tempo collegata a Procida) fanno ritenere che l'isola fosse già abitata intorno al XVI - XV secolo a.C., probabilmente da coloni Micenei.
Sicuramente, intorno al secolo VIII a.C. Procida fu abitata da coloni Calcidesi dell'isola di Eubea; a questi subentrarono in seguito i Greci di Cuma, la cui presenza è confermata da rilevamenti archeologici rinvenuti sull’isola.
Durante la dominazione romana, Procida divenne sede di ville e di insediamenti sparsi sul territorio come le altre isole del Golfo; sembra comunque che in questa epoca non esistesse un vero e proprio centro abitato ma l'isola fu più probabilmente considerata luogo di villeggiatura dei patrizi romani e di coltura della vite.
Dopo la caduta dell'impero Romano, l'isola subì le devastazioni dei Vandali e dei Goti, non cadendo mai in mano longobarda e rimanendo sempre sotto la giurisdizione del duca bizantino di Napoli, nel territorio della Contea di Miseno.
In quest'epoca l'isola cominciava intanto a mutare radicalmente la sua composizione demografica, divenendo luogo di rifugio per le popolazioni in fuga dalle devastazioni dovute all'invasione longobarda prima e, in seguito, alle scorrerie dei pirati saraceni.
Mutava pertanto radicalmente anche l'aspetto dell'isola e al tipico insediamento "diffuso" di epoca romana faceva posto un borgo fortificato tipico dell'età medievale.
La popolazione si rifugiò infatti sul promontorio della Terra, naturalmente difeso da pareti a picco sul mare e in seguito più volte fortificato, mutando così il nome prima in Terra Casata e poi in quello odierno di Terra Murata.
Con la conquista normanna del meridione d'Italia, Procida sperimentò anche il dominio feudale; l'isola, venne assoggettata alla famiglia di origine salernitana dei Da Procida, che la controllarono  per oltre due secoli. Di questa famiglia l'esponente di maggior spicco fu sicuramente Giovanni Da Procida, consigliere di Federico II di Svevia e animatore della rivolta dei Vespri Siciliani.
Nel 1339, l'ultimo discendente dei Da Procida vendette il feudo (con l'isola d'Ischia) alla famiglia di origine francese dei Cossa, famiglia di ammiragli fedele alla dinastia D'Angiò, allora regnante su Napoli. Dei Cossa, esponente di maggior rilievo fu Baldassarre Cossa, eletto antipapa nel 1410 con il nome di Giovanni XXIII.
Durante la dominazione di Carlo V a Napoli l'isola fu confiscata all'ultimo Cossa e concessa in feudo alla famiglia dei d'Avalos d'Aquino d'Aragona (1529), fedele alla casa d'Asburgo. Il primo feudatario fu appunto Alfonso d'Avalos, marchese del Vasto e generale di Carlo V, cugino di Fernando Francesco d'Avalos.
Continuavano intanto anche in quest'epoca le scorrerie dei pirati saraceni, accentuate ulteriormente dalla lotta tra gli Ottomani e l'impero spagnolo.
Da ricordare l'incursione del 1534, ad opera del pirata Kahir-Ad-Din, detto il Barbarossa e successivamente ad opera di Dragut.
Testimonianze di questo periodo sono le torri di avvistamento sul mare, diventate in seguito il simbolo dell'isola, una seconda cinta muraria attorno al borgo della Terra Murata e l'inizio della costruzione del Castello D'Avalos (1563), ad opera degli architetti Giovan Battista Cavagna e Benvenuto Tortelli.
Nel XVII secolo l'isola venne occupata dalla flotta francese comandata da Tommaso Francesco di Savoia, sullo sfondo delle vicende legate alla rivolta di Masaniello e della nascita della seguente Repubblica.
Con l'avvento dei Borbone nel Regno di Napoli, nel 1734, si aveva intanto un ulteriore miglioramento delle condizioni socio-economiche dell'isola, dovuto anche all'estinzione della feudalità nel 1744 per opera di Carlo III, che inserì Procida tra i beni della corona, facendone una sua riserva di caccia.
Nel 1799 Procida prende parte ai movimenti che portano alla proclamazione della Repubblica Napoletana ma al ritorno dei Borbone, pochi mesi dopo, dodici Procidani, tra i più influenti e in vista dell'isola, furono impiccati nella stessa piazza dove era stato issato l'albero della libertà.
Negli anni successivi, l'isola vede diverse volte la guerra passare sul suo territorio con pesanti scontri e devastazioni, a causa della sua basilare posizione strategica nella guerra sul mare, contesa tra Francesi e Inglesi; le cronache riportano che nel solo 1809 circa 4000 persone abbandonarono l'isola al seguito delle navi inglesi sconfitte al termine della sesta coalizione antifrancese.
Il XX secolo vede la crisi irreversibile della cantieristica procidana che nel passato la resero famosa in tutto il mondo, dovuta alla concorrenza dei grandi agglomerati industriali.
Nel 1907 inoltre, Procida perde il suo territorio di terraferma, che diventa un comune autonomo denominato “Monte di Procida”.
Negli ultimi anni l'economia rimane in gran parte legata alla marineria accanto ad una piccola  crescita, dell'industria turistica.