Το βενετσιάνικο φρούριο της Φορτέτζας είναι κτισμένο πάνω στο λόφο του Παλαιοκάστρου, στα δυτικά της σημερινής πόλης. Στο λόφο αυτό υπήρχε η ακρόπολη της αρχαίας πόλης της Ρίθυμνας και το ιερό της Ροκκαίας Αρτέμιδος. Τα λαξεύματα που εντοπίστηκαν σε διάφορα σημεία του λόφου, μαρτυρούν την ύπαρξη της ακρόπολης πάνω στο βράχο. Ο οικισμός μάλλον βρισκόταν κοντά στο λιμάνι. Ωστόσο δεν έχουμε στοιχεία ούτε για τη μορφή του οικισμού, ούτε για τη μορφή της ακρόπολης και του ιερού.
Το φρούριο της Φορτέτζας κατασκευάστηκε μεταξύ 1573-1580 από τους Βενετούς, προκειμένου να προστατεύσει τους κατοίκους από την Τουρκική απειλή. Έχει αστερόμορφο σχήμα, τρεις πύλες και έξι προμαχώνες. Επιλέχθηκε ο λόφος Παλαιόκαστρο, που έχει απέραντη θέα και από στεριά και από θάλασσα.Το συνολικό μήκος του είναι 1307 μ. και περιλαμβάνει τέσσερις προμαχώνες και τρεις αιχμές. Για την ολοκλήρωσή του χρειάστηκαν 76800 αγγαρείες των κατοίκων όλου του νομού και κατασκευάστηκε από κανονικές ορθογωνικές πέτρες από τον πρωτομάστορα Γ. Σκορδίλη. Στο κέντρο ο ναός του S. Nicolo μετατράπηκε στο Τζαμί του Σουλτάν Ιμπραήμ Χάν. Υπήρχε το οίκημα του Διοικητή, του Συμβούλου, χώροι στρατωνισμού και σταυλισμού, αποθήκες πυρομαχικών, δεξαμενή ύδρευσης και κατοικίες που καταστάφηκαν μεταγενέστερα.
Το κάστρο της Φορτέτζας, στο οποίο μεχρι σήμερα δεν έχουν πραγματοποιηθεί συστηματικές ανασκαφές, «φιλοξενεί» τους εξής χώρους :