Only a short time after the destruction of the second church, Justinian the Great suppressed the riots, and set about rebuilding what was damaged and destroyed. 

He commissioned two men, Anthemius of Tralles and the Elder Isidore of Miletus to build a third church at the same location which would be greater than its previous predecessors. Anthemius and Isidore were not referred as architects, but they were called “mechanikoi” which means the masters of the science of the mechanics. Indeed, Anthemius was a mathematician and physicist, and Isidore was a professor of geometry and mechanics. None of them is known to have any building experience before Hagia Sophia. However, they created one of the most significant monuments on earth. 

The construction started only a short while after the end of the Nika Revolt. Many materials had been brought from all over the empire, including yellow stone from Syria, porphyry from Egypt and Hellenic Columns from the Artemis Temple in Ephesus. More than ten thousand people worked for the construction and the third church was inaugurated by the emperor on 27 December 537. The mosaics were finished later on, during the reign of Justin II (565-578).

Several earthquakes happened and gave damaged to Hagia Sophia. The earthquakes on August 553 and December 557 caused cracks in the main dome and the eastern half-dome, and with the earthquake on 7 May 558, the main dome collapsed completely while destroying the ambon, the altar and the ciborium over it. This time it was Isodorus the Younger, the nephew of Isidore of Miletus, who was going to rebuild the dome. He elevated the dome by 6,25 meters, which got its current height today , totally 55,6 meters. With the presidency of the Patriarch Eutcyhius, the cathedral opened again on 23 December 562. It became the seat of the Orthodox patriarch of Constantinople, also imperial ceremonies were held there.

In 726, all the icons, religious pictures and statues were removed from Hagia Sophia by the orders of Emperor Leo the Isaurian, as he was agains the veneration of the images. Emperor Theophilius (829-842) who had interest in Islamic art had monograms installed at the southern entrance of the church.

Hagia Sophia took damage with the fire in 859, following an earthquake on 869. At this earthquake, a half dome collapsed, but then repaired by the order of Emperor Basil I. In 25 October 989, the dome of the basilica again got damaged by an earthquake. This time the Emperor was Basil II, and he ordered the architect Trdat to repair the dome. The construction finished in 13 May 994.

On the fourth Crusade, Hahia Sophia was ransacked by the Latin Christians and many materials and important relics were taken to museums in West. With the Latin occupation of Constantinople between 1204 and 1261, the church became a Roman Catholic cathedral. In 1261, Byzantines captured Constantinople again. In 1317, emperor Andronicus ordered four new buttresses in the eastern and northern parts of the church. 

With the earthquake in 1344, the dome got new cracks, and the earthquake on 19 May 1346 made the several parts of the building collapse. The construction and repairs held by architects Astras and Peralta and finished in 1354. Till that time, the church remained closed.