Η εκκλησία της Αγίας Αικατερίνης βρίσκεται στην Εβραϊκή συνοικία της Μεσαιωνικής Πόλης, κοντά στον τομέα μάχης της "γλώσσας" της Προβηγκίας. Ήταν ο πρώτος ορθόδοξος ναός που μετατράπηκε σε τζαμί από τον σουλτάνο Σουλεϊμάν το Μεγαλοπρεπή, γεγονός στο οποίο οφείλεται και η ονομασία Ιλκ Μιχράμπ (πρώτο προσκύνημα).

Ο αρχικός πυρήνας της εκκλησίας ήταν μονόχωρος καμαροσκεπής. Το βόρειο και νότιο κλίτος προστέθηκαν σε επόμενες οικοδομικές φάσεις και έτσι, στη σημερινή της μορφή, η Αγία Αικατερίνη είναι τρίκλιτος ναός καμαροσκέπαστος. Τα τρία διαμερίσματα επικοινωνούν μεταξύ τους μέσω μεγάλων ημικυκλικών τόξων που καλύπτονται με ισάριθμες ισοϋψείς καμάρες.

Στο εσωτερικό του μνημείου διακρίνονται τρία ζωγραφικά στρώματα. Οι τοιχογραφίες του μεσαίου κλίτους (η Δέηση στο τεταρτοσφαίριο της αψίδας, οι Συλλειτουργούντες Ιεράρχες στον ημικύλινδρο, σκηνές του Δωδεκαόρτου στην καμάρα και ολόσωμοι άγιοι στους τοίχους) χρονολογούνται στο τελευταίο τέταρτο του 14ου αι. και αντικατοπτρίζουν τις υψηλής ποιότητας τάσεις της παλαιολόγειας ζωγραφικής. Από το στρώμα αυτό αξίζει να σημειωθεί η παράσταση των δωρητών, δεξιά και αριστερά από τη στηθαία μορφή του Χριστού, ψηλά στο δυτικό τοίχο.

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