Το βενετσιάνικο φρούριο της Φορτέτζας είναι κτισμένο πάνω στο λόφο του Παλαιοκάστρου, στα δυτικά της σημερινής πόλης. Στο λόφο αυτό υπήρχε η ακρόπολη της αρχαίας πόλης της Ρίθυμνας και το ιερό της Ροκκαίας Αρτέμιδος. Τα λαξεύματα που εντοπίστηκαν σε διάφορα σημεία του λόφου, μαρτυρούν την ύπαρξη της ακρόπολης πάνω στο βράχο. Ο οικισμός μάλλον βρισκόταν κοντά στο λιμάνι. Ωστόσο δεν έχουμε στοιχεία ούτε για τη μορφή του οικισμού, ούτε για τη μορφή της ακρόπολης και του ιερού.

Στους επόμενους αιώνες η πόλη του Ρεθύμνου αναπτύχθηκε στο ίδιο σημείο. Το Castel Vecchio, ο μικρός οχυρωμένος οικισμός της βυζαντινής εποχής, διατηρήθηκε έως τα μέσα περίπου του 16ου αιώνα. Το 1540 είχε αρχίσει η κατασκευή νέου οχυρωματικού τοίχου που θα προστάτευε και το βούργο, που είχε εξαπλωθεί εκτός του Castel Vecchio. Όμως η επιδρομή των Τούρκων το 1571 και η καταστροφή της πόλης, έκανε επιτακτική την ανάγκη για νέα οχυρωματικά έργα, αφού το χερσαίο τείχος δεν την κάλυπτε. Το 1573 θεμελιώθηκε η Φορτέτζα, πάνω στο λόφο του Παλαιοκάστρου. Ο αρχικός σκοπός της κατασκευής ήταν να περιλάβει όλες τις κατοικίες της πόλης, κάτι το οποίο δεν έγινε τελικά. Οι κάτοικοι της πόλης μετά την απομάκρυνση του τούρκικου κινδύνου, άρχισαν να ξανακτίζουν τα σπίτια τους.

Οι εργασίες στο χώρο της Φορτέτζας ολοκληρώθηκαν γύρω στο 1580. Μέσα στο κάστρο εγκαταστάθηκε μόνο η βενετική φρουρά, αφού ο χώρος που απέμεινε για την κατασκευή ιδιωτικών κατοικιών, μετά την ολοκλήρωση των δημόσιων κτιρίων, ήταν τελικά πολύ μικρός. Η έκταση πάνω στην οποία κτίστηκε το κάστρο ήταν ούτως ή άλλως περιορισμένη. Αυτό είχε συνέπειες στη γενικότερη οργάνωση του φρουρίου. Το βραχώδες έδαφος, η ανυπαρξία τάφρου και η μικρή έκταση του ελεύθερου χώρου μπροστά από το φρούριο (spianata), καθιστούσαν τη Φορτέτζα ευάλωτη αμυντικά. Ακόμα και η μορφή των τεσσάρων προμαχώνων του φρουρίου δεν είναι πλήρης, καθώς δεν περιλαμβάνει τα απαραίτητα στοιχεία ενός πλήρους προμαχώνα. Ωστόσο κάποιες από τις αδυναμίες της καλύπτονταν από την μελετημένη οργάνωση του εσωτερικού χώρου. Κοντά στον περίβολο δεν υπήρχαν κτίρια και η νότια πλευρά, η πλέον εκτεθειμένη σε επιθέσεις, προστατευόταν από επιπρομαχώνες (cavalieri). Οι αποθήκες των πυρομαχικών βρίσκονταν στη βόρεια πλευρά, ενώ τα απαραίτητα για την πολιορκία κτίρια είχαν διαταχθεί στη νότια.

Μετά το 1646 και την κατάληψη της πόλης από τους Τούρκους, η Φορτέτζα δεν θα υποστεί μεγάλες αλλαγές. Έγιναν προσθήκες και συμπληρώσεις στις επιχωματώσεις και τον περίβολο του φρουρίου. Αυξήθηκε όμως ο αριθμός των κατοικιών που χτίστηκαν μέσα στο κάστρο. Στις αρχές του 20ου αιώνα το εσωτερικό της Φορτέτζας ήταν σχεδόν εξολοκλήρου οικοδομημένο. Σταδιακά ξεκίνησε η μεταφορά των κατοίκων έξω από το φρούριο και η κατεδάφιση των ερειπωμένων κτισμάτων, από το Δήμο Ρεθύμνου. Στο μεταξύ ο Δήμος, η Αρχαιολογική Υπηρεσία και ο ΕΟΤ απαλλοτρίωσαν αυτές τις εκτάσεις.

Σήμερα το φρούριο της Φορτέτζας αποτελεί το πιο σημαντικό μνημείο του Ρεθύμνου, σήμα κατατεθέν της πόλης. Στα αναστηλωμένα κτίριά του φιλοξενεί πολιτιστικές εκδηλώσεις, εκθέσεις, ενώ στον προμαχώνα του Προφήτη Ηλία βρίσκεται το μικρό Δημοτικό Θέατρο "Ερωφίλη".