Κοντά στα ανατολικά τείχη της Άνω Πόλης, ανάμεσα στις οδούς Ηροδότου και Αποστόλου Παύλου, περικλείεται από περίβολο ο Άγιος Νικόλαος Ορφανός, μετόχι της Μονής Βλατάδων, υπαγόμενο στο Πατριαρχείο, και άλλοτε καθολικό μονής. Από το μοναστηριακό συγκρότημα σώζονται λείψανα του προπύλου προς την οδό Ηροδότου.

Η προσωνυμία "Άγιος Νικόλαος Ορφανός" και "Άγιος Νικόλαος των Ορφανών" απαντά σε πηγές του 17ου και 18ου αιώνα και συσχετίστηκε είτε με τον άγνωστο ιδρυτή του ναού και την οικογένειά του είτε με την ιδιότητα του Αγίου Νικολάου ως προστάτη των χηρών και των ορφανών. Η ανέγερση του μνημείου πιθανώς προσδιορίζεται χρονικά από την τοιχογράφηση του που εντάσσεται ανάμεσα στα 1310-1320.

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

Ο αριστουργηματικός τοιχογραφικός διάκοσμός του είναι ένα από τα πληρέστερα διατηρούμενα σύνολα στη Θεσσαλονίκη. Στον κυρίως ναό απεικονίζονται σκηνές του Δωδεκαόρτου, των Παθών, του Αναστάσιμου και του λειτουργικού κύκλου και μορφές αγίων. Σκηνές του Ακαθίστου Ύμνου κοσμούν τη βόρεια στοά, ο Βίος του αγίου Νικολάου και Μηνολόγια τη δυτική, ενώ ορισμένα θαύματα του Χριστού, οι προεικονίσεις της Θεοτόκου και ο βίος του Αγίου Γερασίμου του Ιορδανίτη τη νότια. Οι αφηγηματικές σκηνές χαρακτηρίζονται από γραφικότητα και ζωηρότητα, ενώ οι σκηνές του Πάθους από δραματική ένταση. Στις μεμονωμένες μορφές αναδεικνύεται ο όγκος, η λεπτότητα των χαρακτηριστικών και ο χρωματικός πλούτος. Οι τοιχογραφίες του ναού αποτελούν έργο της ώριμης παλαιολόγειας Αναγέννησης που συνδέεται με τον καλλιτεχνικό κύκλο των Θεσσαλονικέων ζωγράφων Γεωργίου Καλλιέργη, Μιχαήλ Αστραπά και Ευτύχιου. Ο δημιουργός τους πιθανώς ταυτίζεται με εκείνον που φιλοτέχνησε το καθολικό της σερβικής μονής Χελανδαρίου την εποχή του Μιλιούτιν (1314).

Η απεικόνιση στον κυρίως ναό του αγίου Γεωργίου του Γοργού, προστάτη της οικογένειας του Μιλιούτιν, και του αγίου Κλήμη Αχρίδας -θέματα αγαπητά στη σερβική εικονογραφία- και οι σχέσεις του Σέρβου κράλη με τη Θεσσαλονίκη και την αυτοκρατορική οικογένεια του Ανδρόνικου Β΄ οδήγησαν στo συσχετισμό της τοιχογράφησης του ναού με το Σέρβο ηγεμόνα αποδεικνύοντας τον κεντρικό ρόλο της Θεσσαλονίκης στην τέχνη των Βαλκανίων.

Η λειτουργία της μονής συνεχίστηκε και επί Τουρκοκρατίας. Οι τοιχογραφίες της αποκαλύφθηκαν το 1957-1960 κατά τις εργασίες αποκατάστασης του μνημείου.