Через один или два года после этого в жизни Юстиниана наступил новый поворотный момент — встреча с будущей императрицей. Отец Феодоры содержал медведей на ипподроме, ее мать была акробаткой — уже этого хватало с избытком, чтобы закрыть ей путь в высшее общество. Но и в биографии самой Феодоры имелось много чего интересного. Будучи совсем юной, она вместе с тем обрела славу самой отъявленной куртизанки Константинополя. Перу ее современника Прокопия принадлежит весьма откровенная характеристика Феодоры — вряд ли в мировой истории писалось в отношении королевы или императрицы что-либо подобное:
«Когда Феодора была еще слишком незрела, чтобы вступать в половые отношения как женщина, она действовала так, как мог бы действовать проститутка-мужчина — чтобы таким неестественным образом удовлетворить тех подонков общества, которые проводили свое время в публичном доме… Но как только она достигла зрелости, то стала настоящей шлюхой. Никогда ни одна женщина не предавалась плотским утехам с такой неутомимой страстью. Не раз она посещала пиршества с десятью и более мужчинами — все они были одержимы страстью к блуду и находились на пике своих сил. И она возлежала со своими спутниками целую ночь. Когда же она доводила их до истощения, то шла к их слугам — иногда их число достигало тридцати — и совокуплялась с каждым по очереди, но даже тогда не могла удовлетворить свою похоть. И хотя она использовала три отверстия в своем теле, она обыкновенно жаловалась на то, что природа не снабдила ее более крупными отверстиями в сосках, так чтобы она могла затеять новую форму половых сношений. Зачастую в театре, на виду у всех… она ложилась на спину, и специально подготовленные для этого рабы посыпали зернами ячменя ее половые органы, а натренированные для этой задачи гуси склевывали зерна одно за другим».
Став любовницей чиновника среднего ранга, она вместе с ним поехала в Северную Африку. Получив отставку после очередной жестокой семейной ссоры, Феодора заработала себе денег на обратный путь тем единственным способом, который знала. Но, находясь в Александрии, она, по-видимому, познакомилась с некоторыми серьезными клириками и, возможно, даже обрела определенный религиозный опыт. Похоже, что она вернулась в Константинополь уже совсем другим человеком. Но одна черта Феодоры совершенно точно осталась неизменной — ее сильная привязанность к партии Синих. Юстиниан также благоволил Синим, и, возможно, при их посредничестве он впервые повстречал Феодору — на тот момент она была на середине своего четвертого десятка. Эта женщина сразу же пленила его, и он решил взять ее в жены.
Препятствием к браку стало крайне враждебное отношение к Феодоре императрицы. Люпицина, обнаружив наконец женщину, имеющую еще более низкое происхождение, чем она, стала унижать Феодору всеми возможными способами. Но в 524 г. императрица умерла, и в 525 г. Юстиниан и Феодора венчались в соборе Св. Софии. 4 апреля 527 г. они были коронованы как соправитель императора и императрица, а когда 1 августа скончался и Юстин, Юстиниан и Феодора оказались единственными верховными правителями Византийской империи. Акцентирование множественного числа здесь очень важно. Феодора стала не просто императрицей-супругой, а по настоянию Юстиниана правила вместе с ним; муж и жена советовались друг с другом, принимали совместные решения по всем важнейшим государственным делам.
Нам неизвестно, что константинопольцы думали о браке Юстиниана. Но наверняка в глазах многих такой мезальянс представлялся позором для империи. Впрочем, Юстиниан и без того пользовался любовью народа, который оплачивал из своего кармана весьма дорогостоящие акции императора. Так было с войной с Персией; так было с «Вечным миром» 532 г., которым она закончилась, — по этому соглашению византийцы выплачивали ежегодную дань персам в 11 000 фунтов золота (что никогда не афишировалось). Так было и с монументальной программой строительства религиозных сооружений, которую Юстиниан начал с возведения величественной церкви, посвященной Богоматери Влахернской, в том месте, где Феодосиева стена нисходила к Золотому Рогу, — продолжением этой программы стало восстановление еще семи церквей. А в первые же дни после восшествия на престол он построил в память о святых мучениках Сергии и Вакхе церковь, которая по своему великолепию уступала в Константинополе только собору Св. Софии.