Πρώτη φροντίδα του Ιουστινιανού, μετά τη «στάση του νίκα», ήταν να χτίσει ό,τι καταστράφηκε και να κάνει την Πόλη ακόμη καλύτερη. Το πιο σημαντικό από τα έργα του ήταν ο ναός της Αγίας Σοφίας.
Ανέθεσε το χτίσιμο της σε δυο ονομαστούς αρχιτέκτονες, τον και τον . Επιθυμία και εντολή του ήταν ο ναός της Σοφίας του Θεού να χτιστεί έτσι, ώστε να ζήσει αιώνες και όμοιος του να μην υπάρχει πουθενά.
Οι δύο αρχιτέκτονες, για να πρωτοτυπήσουν, συνδύασαν το ρυθμό της , με τον οποίο είχαν χτιστεί οι πρώτοι χριστιανικοί ναοί, και του ναού με . Έτσι γεννήθηκε το σχέδιο της Αγίας Σοφίας και ο νέος ρυθμός, η βασιλική με τρούλο. Ο ρυθμός αυτός επηρέασε την αρχιτεκτονική των ναών τόσο, ώστε ακόμη και στις μέρες μας πολλοί ναοί να κτίζονται με αυτό το σχέδιο.
Ο Ιουστινιανός ήθελε το ναό αυτό να τον νιώθουν δικό τους όχι μόνο οι κάτοικοι της αλλά όλης της . Γι' αυτό ζήτησε απ' όσους επιθυμούσαν να προσφέρουν και για το χτίσιμο του. Πολύτιμα και υλικά από κάθε γωνιά του κράτους προσφέρθηκαν και μεταφέρθηκαν στην Πόλη. χιλιάδες και διαλεχτοί εργάστηκαν χρόνια χωρίς διακοπή, για να ολοκληρώσουν το έργο.
Η Αγία Σοφία εγκαινιάστηκε το μ.Χ. και ήταν, όπως την είχε ονειρευτεί ο δημιουργός της, η καλύτερη στον κόσμο. Ο Ιουστινιανός, όταν προσήλθε στο ναό την ημέρα των εγκαινίων, σήκωσε εντυπωσιασμένος τα μάτια του στον ουρανό και ψιθύρισε: «νενίκηκά σε Σολομώντα!».
Στους αιώνες που ακολούθησαν ο ναός στέγασε όλες τις και τις της Πόλης και της αυτοκρατορίας. Εκεί στέφονταν οι και οι και τελούνταν οι δοξολογίες των . Εκεί γίνονταν και οι του λαού προς την Παναγία για τη της Πόλης, στις ώρες των κινδύνων που την απειλούσαν.