Το έτος 1646 το Ρέθυμνο πολιορκήθηκε και κατακτήθηκε από ένα μεγάλο εκστρατευτικό σώμα των Οθωμανών, το οποίο ακολουθούσαν δερβίσηδες, κήρυκες δηλαδή, του σουφιστικού, μυστικιστικού Ισλάμ, οι οποίοι προσεύχονταν για να εμψυχώνουν τους στρατιώτες. Στη διάρκεια της πολιορκίας, μεγάλο τμήμα του εκστρατευτικού σώματος των Οθωμανών, και οι δερβίσηδες που το ακολουθούσαν, στρατοπέδευε στον Μασταμπά, από όπου εισέβαλε και στην πόλη του Ρεθύμνου. Μετά την κατάκτηση της πόλης ο σεΐχης Μουσταφάς, ο οποίος ανήκε στο σουφιστικό τάγμα των Καντιρήδων, έχτισε στη θέση αυτή έναν τεκέ, ένα συγκρότημα διαμονής δερβίσηδων, που, με το τζαμί, έμεινε γνωστό στην ιστορία ως το Τζαμί του Βελή Πασά, το οποίο σήμερα σώζεται στη συνοικία του Μασταμπά. Ο Βελή Αγάς, που ανήλθε στη συνέχεια στο αξίωμα του Πασά, ήταν τότε υπασπιστής του πορθητή του Ρεθύμνου βεζίρη Χουσεΐν Πασά, και ανέλαβε να χρηματοδοτήσει την οικοδόμηση του τεκέ, ο οποίος αργότερα πήρε και το όνομά του. Η παλαιότερη αναφορά που έχουμε για το συγκεκριμένο τζαμί εντοπίζεται το 1651, στο κατάστιχο του καδή του Ρεθύμνου. Με το πέρασμα του χρόνου, πολλοί ήταν εκείνοι που θαύμασαν και μνημόνευσαν αυτό το ιστορικό μνημείο, που λειτουργούσε ως προσκύνημα για τους μουσουλμάνους του Ρεθύμνου. Ένας από αυτούς ήταν και ο γνωστός Οθωμανός περιηγητής Εβλιά Τσελεμπή, ο οποίος τότε πραγματοποιούσε ταξίδια σε όλη την Οθωμανική Αυτοκρατορία. Ο Εβλιά, λοιπόν, γράφει ότι ο τεκές του Βελή Πασά ήταν ένα από τα τρία ιδρύματα του Ρεθύμνου που «μέρα και νύχτα προσέφεραν σούπα σε πλούσιους και φτωχούς, ηλικιωμένους και νεαρούς». Στον τεκέ λοιπόν οι δερβίσηδες μαγείρευαν και παρέθεταν γεύματα.

Το συγκρότημα του Βελή Πασά αποτελείται από το τζαμί στα νότια, οκτώ θολοσκεπή κελιά στα δυτικά και ένα διώροφο κτίσμα στα βόρεια τοποθετημένα σε ήπια επικλινές έδαφος. Το τζαμί έχει σχεδόν τετραγωνική κάτοψη με διαστάσεις 16,60 x 16,20 μ. και ανήκει στον πολύτρουλο τύπο με προστώο. Στεγάζεται με έξι μικρούς τρούλους, οι οποίοι εδράζονται σε ένα σύστημα από οξύκορφα τόξα και ημιχώνια, τοποθετημένα ανά τρία με προσανατολισμό ΒΔ-ΝΑ. Καταλήγει βορειοδυτικά στο προστώο, το οποίο αποτελείται από ανοικτή τοξοστοιχία που συνθέτουν τρεις οξύκορφες αψίδες και στεγάζεται με τρεις τρούλους (θόλους). Η μορφολογία των αψίδων συνδέεται ίσως με τοπικούς χτίστες, διατηρώντας την οικοδομική γλώσσα της βενετικής αρχιτεκτονικής. Η είσοδος στο τετραγωνικό κτίριο πραγματοποιείται μέσω μίας εντυπωσιακής πύλης από ντόπιο ασβεστόλιθο με ανάγλυφη φυτική διακόσμηση, που θεωρείται ότι προέρχεται από μία γειτονική εκκλησία από τον οικισμό του Μπούργκου που εγκαταλείφθηκε στη διάρκεια της οθωμανικής πολιορκίας του Ρεθύμνου. Στη δυτική πλευρά βρίσκεται η τοξωτή θύρα πρόσβασης στον μιναρέ, που διαμορφώνεται με ένα πλατύσκαλο στο οποίο καταλήγει μία λίθινη κλίμακα. Στην κάθε πλευρά του τετραγωνικού κτίσματος ανοίγονται δύο ορθογώνια παράθυρα, εκτός από τη δυτική. Στο μέσον του νοτιοανατολικού τοίχου τοποθετείται το μιχράμπ, η κόγχη της προσευχής των μουσουλμάνων, με κατεύθυνση τη Μέκκα. Ο μιναρές βρίσκεται σε επαφή με το κτίριο στη ΒΔ γωνία του και διαθέτει έναν μόνον εξώστη. Σύμφωνα με την σωζόμενη επιγραφή του έχει χτιστεί το έτος Εγίρας 1204 (1789/90). Η επιγραφή αναφέρει τα εξής: Να μη βασκαθεί! Δόξα και ευγνωμοσύνη στον Κύριο… Κάναμε δωρεά και ανακαινίσαμε τον μιναρέ για να ακούγεται το εζάνι (το κάλεσμα στην προσευχή) και για την ελεημοσύνη του Θεού. Στη δυτική πλευρά της αυλής του τεκέ και σε ένα υψηλότερο επίπεδο υπάρχουν τα οχτώ θολοσκέπαστα κελιά, πανομοιότυπα γεωμετρικά και μορφολογικά, στα οποία διέμεναν οι δερβίσηδες. Το διώροφο κτίριο που βρίσκεται στη βόρεια πλευρά ως φυσική προέκταση διαθέτει απλή αρχιτεκτονική μορφή και χρησίμευε πιθανόν ως ο χώρος κατοικίας του ηγουμένου του τεκέ και κουζίνα για την προετοιμασία των γευμάτων. Η κρήνη βρισκόταν στην είσοδο του περιβόλου, επιτελώντας βασικό ρόλο στον τελετουργικό καθαρμό πριν από την έναρξη της προσευχής.

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