Το κτηριακό συγκρότημα το οποίο απαρτίζεται σημερα από τρία επί μέρους κτήρια, όπου στεγάζονται η Νομαρχιακή Αυτοδιοίκηση, τα Δικαστήρια και η Διεύθυνση της Αστυνομίας, είναι αποτέλεσμα της μετασκευής τούρκικου κτίσματος του τέλους του 19ου αι. Το συγκρότημα δεσπόζει στην πλατεία Ελευθερίας και αναπτύσσεται κατά μήκος της νότιας παρειάς της λεωφόρου Δικαιοσύνης.

Το πρώτο κτίσμα που κατασκευάσθηκε στη θέση αυτή ήταν βενετικό. Οι Βενετοί την έβδομη δεκαετία του 16ου αι. κατασκεύασαν τους στρατώνες του Αγίου Γεωργίου, που είχαν δυνατότητα στέγασης 700 στρατιωτών. Το κτήριο, μετά από τις προσθήκες που έγιναν σε αυτό τον 17ο αι. έφτασε να έχει μήκος 261 μ., διέθετε 200 δωμάτια και είχε ένα μεγάλο επίμηκες στεγασμένο προστώο κατά μήκος της βόρειας πλευράς του. Μετά την πτώση του Χάνδακα στους Τούρκους οι βενετικοί στρατώνες χρησιμοποιήθηκαν από τους νέους κατακτητές. Καταστράφηκαν όμως κατά τον μεγάλο σεισμό του 1856. Στην ίδια θέση οι Τούρκοι αποφάσισαν να κατασκευάσουν νέους στρατώνες. Τα σχέδια εκπονήθηκαν από τον Αθανάσιο Μούση, στον οποίο οφείλεται ο σχεδιασμός και άλλων λαμπρών κτιρίων της πόλης, με κορυφαία ανάμεσά τους τον μητροπολιτικό ναό του Αγίου Μηνά και το Βεζίρ Τζαμί, τον σημερινό ναό του Αγίου Τίτου. Ο θεμέλιος λίθος των νέων στρατώνων τέθηκε το 1883. Το κτήριο, που ήταν γνωστό με την τούρκικη ονομασία ''κισλάδες'', ήταν διώροφο, επίμηκες και ενιαίο. Στεγαζόταν με ξύλινη κεραμοσκεπή στέγη. Στον μέσον της βόρειας όψης του εντοιχίστηκε το περίφημο μαρμάρινο αναγεννησιακό θύρωμα ενός παρεκκλησίου του καθολικού της ενετικής μονής του Αγίου Φραγκίσκου. Το θύρωμα αυτό, δώρο του Κρητός Πάπα Αλεξάνδρου Ε' προς τη μονή τη δεύτερη δεκαετία του 15ου αι. αφαιρέθηκε από την αρχική του θέση και τοποθετήθηκε στη νέα όταν άρχισαν να κτίζονται οι τούρκικοι στρατώνες. Αυτό έγινε κατά τη διάρκεια του σεισμού του1856.

Μετά την αυτονομία και την αποχώρηση του τουρκικού στρατού, στους παλαιούς στρατώνες στεγάσθηκε το ''Γυμνάσιον Ηρακλείου'' ενώ αργότερα, το 1921, στεγάστηκε και το δεύτερο γυμνάσιο της πόλης. Στα τέλη της δεκαετίας του 1920, με σχέδια του αρχιτέκτονα Δημήτρη Κυριακού, το τούρκικο κτήριο υφίσταται εκτεταμένες τροποποιήσεις ώστε να λειτουργήσει ως σύγχρονο διοικητήριο. Έτσι το ενιαίο κτίσμα χωρίζεται σε τρία επιμέρους τμήματα, ανάμεσα στα οποία δημιουργούνται ευρείες υπαίθριες διαβάσεις. Τα ξύλινα πατώματα και η ξύλινη στέγη αντικαθίστανται με πλάκες από οπλισμένο σκυρόδεμα και οι όψεις του μορφολογούνται σύμφωνα με τις επιταγές του κλασικισμού.