La Fortezza veneziana è sita sulla collina “Paleokastro”, sul lato ovest della città. Questa è la stessa collina sulla quale era situata l''Acropoli della città antica di Rithymna, insieme a un santuario dedicato alla dea Artemide.

La Fortezza fu costruita tra il 1573-1590 dai veneziani al fine di proteggere i cittadini dalla minaccia turca.

Due anni dopo la distruzione della città, nel settembre del 1573, il Rettore Alvise Lando pose la prima pietra del castello, che doveva essere costruito secondo i progetti di Sforza Palavicini.

Dopo un gran numero di modifiche, la fortezza fu finalmente completata nel 1590.

Il progetto generale della fortezza fornì nuove forme di difesa, necessarie a causa della comparsa della polvere da sparo. La pianta poligonale includeva sei bastioni, mentre le mura erano più ampie e inclinate.

In realtà però, a causa della morfologia del terreno, si poterono costruire solo tre bastioni sui lati sud ed est e tre sulla parete nord. In generale, il progetto del muro di fortificazione non era il migliore possibile, in quanto limitava le capacità difensive. La superficie rocciosa, che impediva di costruire in modo adeguato, la mancanza di un fossato, lo spazio libero limitato intorno alla fortezza, conseguenza del rifiuto degli abitanti di demolire le loro case, sono state alcune delle cause che hanno limitato la riuscita dell''azione difensiva.

L''infrastruttura dello spazio interno era invece ben pianificata. Gli edifici pubblici erano situati a distanza dalle mura, i magazzini di munizioni erano alloggiati presso il sicuro lato nord, e una piazza formava il centro della fortezza.

L''interno della fortezza ospitava i seguenti edifici: il deposito dell''artiglieria, dove venivano conservati i cannoni e le armi, la residenza dei Consiglieri, in cui viveva uno dei due consiglieri veneziani della città, e la residenza del Rettore, un lussuoso, magnifico edificio nella piazza centrale della Fortezza.

La residenza del Rettore, in parte conservata, era situata a ovest della piazza centrale, di fronte alla cattedrale. La costruzione dell''edificio cominciò nel 1575 e venne completata nel 1582. Il primo a viverci fu il Rettore Anzolo Barocci.

Quest''ultimo continuò a modificare l''edificio fino al 1584, perché riteneva che fosse troppo alto ed esposto verso la collina di Aghios Athanassios, nella parte occidentale della città. Lo stile imponente e lussuoso della costruzione è riportato dai documenti scritti di quel tempo, che testimoniano la presenza di 49 porte, 81 finestre, due scale e alcune gallerie.

Purtroppo, nessuno degli edifici di questo complesso si è conservato, ad eccezione di parte della prigione, che Barocci aveva costruito ad est della residenza principale, e della cattedrale di San Nicola, situata di fronte.

Il tempio del sultano Ibrahim fu costruito sulle rovine della cattedrale di San Nicola durante l''occupazione turca. Nuovi elementi, come la grande cupola semicircolare, l''abside della Michrab al centro del lato sud-est, il minareto, situato accanto all''ingresso, hanno caratterizzato la trasformazione della cattedrale in un tempio musulmano.