На месте Святой Софии, как нередко бывает с христианскими святынями, в языческие времена тоже было капище — по всей вероятности, храм Артемиды. Что же касается самой Софии, то сохранившаяся до наших дней церковь Божественной Мудрости — третья по счету. Первую заложил около 330 года сам основатель новой столицы Константин Великий (от нее не осталось ни одного бесспорного фрагмента). Она была освящена в 360 году, но через 44 года сгорела. В 415 году Феодосий II построил на этом же месте новый храм. Но и тот был разрушен в 532 году во время восстания Ника (крупнейшего народного выступления в истории Византии). Жестоко подавив это восстание (истребив около 35 тысяч на располагавшемся неподалеку Ипподроме), за дело взялся тот, при котором Византия вышла на пик своего могущества, — Юстиниан. София стала во многих смыслах храмом-собирателем. Для строительства были привезены остатки многих монументальных сооружений древности Греции и Рима. Из храма Артемиды в Эфесе (того, что некогда был подожжен Геростратом) привезли колонны из зеленого мрамора. Мраморные плиты доставили из древних каменоломен Фессалии, Лаконии, Карии, Нумидии и со знаменитой горы Пентеликон близ Афин, из мрамора которой за десять веков до Айя-Софии был построен на Акрополе Парфенон — храм Девы Афины. Центральные — Императорские — двери, по преданию, сделаны из остатков Ноева ковчега. Юстиниан в тщеславном порыве решил было вымостить пол плитами кованого золота и даже все стены внутри храма намеревался покрыть золотом, но его все же отговорили от этого. Известь для храма разводили на ячменной воде, в цемент добавляли масло, а для верхней доски патриаршего престола был создан материал, которого до того не существовало: в расплавленное золото бросали драгоценные камни — рубины, сапфиры, аметисты, жемчуга, топазы, ониксы. Полностью секреты строительного раствора разгадать не удалось, но налицо вещественное выражение исторического ритма — сначала византийская плоть впитывает золото и драгоценности, потом их оттуда варварски выковыривают завоеватели.
Работа, начатая 23 февраля 532 года, продолжалась 5 лет и 10 месяцев.