Η ολοκλήρωση της αρχικής κατασκευής του τεμένους χρονολογείται μεταξύ των ετών 1579-1580. Κτήτορας του ήταν ο πασάς Φερχάντ Σοκόλοβιτς, από τον οποίο έλαβε το τέμενος την ονομασία του, ενώ σχετικά με τον αρχιτέκτονα, αν και είναι άγνωστος, υποστηρίζεται πως υπήρξε μαθητής του φημισμένου Οθωμανού αρχιτέκτονα Μιμάρ Σινάν. Το αρχικό κτιριακό συγκρότημα επεκτάθηκε στα τέλη του 19ου αιώνα, ενώ τη δεκαετία του 1950 έγιναν ορισμένες εργασίες συντήρησης. Ενδιάμεσα, το τέμενος είχε υποστεί ζημιές από πυρκαγιά που ξέσπασε το 1737, αλλά και από βομβαρδισμό κατά τη διάρκεια του Β΄ Παγκοσμίου Πολέμου. Τον Μάιο του 1993, το τέμενος κατεδαφίστηκε έπειτα από απόφαση των αρχών της Σερβικής Δημοκρατίας, κατά τη διάρκεια του Πολέμου της Βοσνίας[3].
Το 2001 ξεκίνησαν οι εργασίες ανακατασκευής του τεμένους, ενώ η τελετή έναρξης των εργασιών διεκόπη από εκτεταμένα επεισόδια που προκλήθηκαν από την αντίδραση Σέρβων εθνικιστών και οδήγησαν στον θάνατο ενός ατόμου. Ανάλογα επεισόδια πραγματοποιήθηκαν και ένα μήνα αργότερα ανάμεσα σε αστυνομικούς και διαδηλωτές, όταν έγινε η τελετή τοποθέτησης των θεμελίων[2]. Η ανακατασκευή ολοκληρώθηκε το 2016 και βασίστηκε πάνω σε αρχιτεκτονικά σχέδια προηγούμενων εργασιών συντήρησης. Επιπλέον, οι αρχιτέκτονες χρησιμοποίησαν σε μεγάλο βαθμό οικοδομικά υλικά του αρχικού κτιρίου, τα οποία κατάφεραν να εντοπίσουν[4].
Τα εγκαίνια του ανακατασκευασμένου τζαμιού Φερχάτ Πασά πραγματοποιήθηκαν την 7η Μαΐου του 2016, ημέρα κατά την οποία συμπληρώνονταν 23 χρόνια από την καταστροφή του αρχικού κτιρίου[4].
