Το τέμενος ιδρύθηκε το 1467–1468 από τον Οθωμανό στρατιωτικό διοικητή Χαμζά Μπέη προς τιμήν της κόρης του Χαφσά Χατούν. Το τέμενος χτίστηκε ως ένας μικρός, τετράγωνος ευκτήριος οίκος (μεσζίτ) με τρούλο. Στα μέσα και προς τα τέλη του 16ου αιώνα, το κτήριο επεκτάθηκε σημαντικά με την προσθήκη μιναρέ και μιας μεγάλης περίστυλης αυλής (αίθριου), παίρνοντας τη μορφή μεγάλου τζαμιού για να καλύψει τις ανάγκες του αυξανόμενου πληθυσμού. Πρόκειται για το πρώτο τέμενος-τζαμί που χτίστηκε και λειτούργησε ως τέτοιο στη Θεσσαλονίκη, μετά την κατάληψη της πόλης από τους Οθωμανούς (1430).
Το Χαμζά Μπέη τζαμί είναι το μοναδικό στον χώρο της Βαλκανικής που διαθέτει αίθριο, με εξαίρεση τα τζαμιά της Αδριανούπολης και της Κωνσταντινούπολης, που υπήρξαν πρωτεύουσες της αυτοκρατορίας και έδρες του σουλτανάτου. Πρόκειται για το μοναδικό τέμενος με αίθριο, ο κτήτορας του οποίου δεν ήταν σουλτάνος, καθώς αποτελούσε άγραφο προνόμιο των Οθωμανών σουλτάνων να έχουν περίστυλες αυλές στα τζαμιά τους. Η τετράγωνη θολοσκεπής αίθουσα ύψους 17 μ. φωτίζεται από οκτώ τοξωτά παράθυρα και έναν κυκλικό φεγγίτη. Είκοσι δύο μαρμάρινες κολώνες με 15 κιονόκρανα παλαιοχριστιανικών χρόνων (5ος – 6ος αι.) στηρίζουν τις στοές που περιβάλλουν τον αίθριο χώρο.
Το κτίριο έπαψε να λειτουργεί ως τζαμί μετά την απελευθέρωση της Θεσσαλονίκης (1912). Το τέμενος υπέστη πολλές αλλαγές στη μακρόχρονη ιστορία του. Στους χώρους του βρήκαν στέγη πρόσφυγες και τα ίχνη της διαβίωσής τους υπάρχουν ακόμη, όπως για παράδειγμα η μετατροπή της εισόδου στο πατάρι του χώρου προσευχής σε τζάκι. Άλλοι χώροι διαμορφώθηκαν σε καταστήματα, ενώ η μεγαλύτερη παρέμβαση έγινε με τη μετατροπή της αυλής στον κινηματογράφο «Αλκαζάρ», ανοιχτό αρχικά και στη συνέχεια κλειστό, με την τοποθέτηση στέγης πάνω από την αυλή.
Για πολλές δεκαετίες, η σύγχρονη παθολογία του μνημείου οφειλόταν σε πολλούς παράγοντες, ενώ επιβαρύνθηκε και από τον σεισμό του 1978. Από το 2007 και εξής ξεκίνησαν ποικίλες εργασίες τεκμηρίωσης, στερέωσης, αποκατάστασης και προστασίας του μνημείου. Το 2023 το έργο της αποκατάστασης του τεμένους Χαμζά Μπέη εντάχθηκε στο Ταμείο Ανάκαμψης και Ανθεκτικότητας. Η Εφορεία Αρχαιοτήτων Πόλης Θεσσαλονίκης, στο πλαίσιο των επεμβάσεων αποκατάστασης του μνημείου, ανέλαβε την επίβλεψη και τεκμηρίωση των ανασκαφικών εργασιών. Οι εργασίες αποκατάστασης και συντήρησης του μνημείου πραγματοποιήθηκαν από τη Διεύθυνση Αναστήλωσης Βυζαντινών και Μεταβυζαντινών Μνημείων και τη Διεύθυνση Συντήρηση Αρχαίων και Νεωτέρων Μνημείων του Υπουργείου Πολιτισμού.
Το μνημείο πλέον έχει αποκτήσει μια νέα ταυτότητα ως χώρος πολιτισμού, υπό την αιγίδα του Υπουργείου Πολιτισμού, του MOMUS και της Εφορείας Αρχαιοτήτων Πόλης Θεσσαλονίκης.
