Κατὰ τὸ α΄ ἥμισυ τοῦ 6ου αἰῶνος, μετὰ ἀπὸ τρεῖς ὁμαδικὲς σφαγὲς μοναχῶν ἀπὸ βαρβαρικὲς συμμορίες, οἱ Σιναΐτες ἐπισκέπτονται τὴν Κωνσταντινούπολη καὶ προστρέχουν στὸν αὐτοκράτορα τῶν Ρωμαίων Ἰουστινιανό. Τοῦ ζητοῦν νὰ τοὺς κτίσει κάστρο, ὅπως εἶχε κάνει νωρίτερα στὴν Παλαιστίνη γιὰ χάρη τοῦ ἁγίου Σάββα. Ὁ ἀρχιτέκτονας Στέφανος μὲ πλῆθος τεχνιτῶν καὶ ἐργατῶν ἐγκαθίσταται στὴν ἔρημο καὶ ξεκινᾶ τὸ κοπιῶδες πολυετὲς ἔργο τῆς ἀνοικοδομήσεως τοῦ λαμπροῦ ρωμαϊκοῦ κάστρου, χρησιμοποιώντας τὸν τοπικὸ σκληρὸ γρανίτη. Ἀτόφιος ὁ περικαλλὴς Ναὸς καὶ τὸ μεγαλύτερο μέρος τοῦ τείχους μὲ τὶς ἐπάλξεις του διατηροῦνται τελείως ἀναλλοίωτα ἀπὸ τὴν ἐποχὴ ἐκείνη, κυρίως λόγῳ τῆς ἀπουσίας βροχῶν στὴν περιοχή.
Ἐντὸς τῆς Μονῆς τῆς ἁγίας Αἰκατερίνης περικλείεται ἡ Φλεγομένη Βάτος, τὸ πηγάδι τοῦ Μωυσέως καὶ ὁ πύργος τῆς ἁγίας Ἑλένης (4ος αἰών), ὁ ὁποῖος ὑπῆρξε τὸ πρῶτο ὀχύρωμα τῶν Μοναχῶν ἔναντι τῶν διαφόρων ἐπιδρομέων. Ὡς ζωντανὴ συνέχεια τοῦ ἤδη ὑφισταμένου στοιχειώδους μοναστικοῦ συγκροτήματος καὶ σύμφωνα μὲ τὴν μαρτυρία τοῦ ἱστορικοῦ Προκοπίου (στὸ ἔργο του «Περὶ Κτισμάτων») ἡ ἰουστινιάνειος Μονὴ ἦταν ἀφιερωμένη ἀρχικῶς στὴν Θεοτόκο (τὴν ὁποία προετύπωνε τὸ θαῦμα τῆς Ἀκαταφλέκτου Βάτου), παράλληλα ὅμως ἰδιαίτερη τιμὴ ἀπελάμβανε ἀνέκαθεν καὶ ὁ Προφήτης Μωυσῆς.