The new church was designed and built by the architects Anthemius of Tralles and Isidorus of Miletus in the form of a Greek cross with five domes: one above each arm of the cross and one above the central bay where the arms intersected. The western arm of the cross extended westward forming the atrium. The relics of [[Constantine the Great|Constantine]] and the three saints were re-installed in the new church, and a mausoleum for Justinian and his family was built at the end of the northern arm.
For more than 700 years the Holy Apostles was the second-most important church in Constantinople, after the basilica of the Holy Wisdom ([[Hagia Sophia(Constantinople)|Hagia Sophia]]). But whereas the Holy Wisdom was in the oldest part of the city, the Holy Apostles stood in the centre of the newer part of the much expanded imperial capital, on the great thoroughfare called Mese or Centre Street, and was the busiest church in the city. Most Emperors and many [[patriarch]]s and [[bishop]]s were buried in the church and their relics were venerated by the faithful for centuries.
The most treasured possession of the church were the supposed skulls of Saints Andrew, Luke and Timothy, but the church also held relics of Saint John Chrysostom and other Church Fathers, saints and martyrs. The church also held what was believed to be part of the "Column of Flagellation," to which Jesus had been bound and flogged. Over the years the church acquired huge amounts of gold, silver and gems donated by the faithful.