После такого бурного начала жизни Феодора на некоторое время вдруг исчезла. Говорили, что она последовала за своим любовником в Африку, но роман длился недолго, и несчастная вскоре оказалась без средств к существованию в Александрии Египетской, научном и культурном центре тогдашнего мира. Там она, к счастью, попала под влияние среды — предместья Александрии изобиловали монастырями, а в Ливийской пустыне скрывалось столько отшельников, что она заслужила титул «пустыни святых».
Вероятно, именно тогда в Феодоре что-то кардинально изменилось. По слухам, в то время она родила своего единственного ребенка — мальчика или девочку. Во всяком случае, потом, когда Феодора воцарилась на троне, ее внучка занимала вполне достойное положение во дворце.
Когда Феодора вернулась в Константинополь, то начала вести уединенную и вполне нравственную жизнь. Поселившись в скромном домике, она занималась рукоделием и пряла шерсть, зарабатывая этим себе на жизнь. В это время ее встретил Юстиниан и безумно влюбился.
Феодора буквально околдовала Юстиниана. Неизвестно, как ей удалось пленить и прочно привязать к себе этого уже немолодого — ему было около сорока лет — государственного деятеля, который всю жизнь опасался скомпрометировать себя. Говорили о магии и любовных напитках, но, вероятнее всего, дело было в живом уме, непринужденной грации, остроумии и сильной воле. Все вместе это должно было очень сильно подействовать на нерешительного мужчину. Влюбленный без памяти, он исполнял все требования Феодоры. Она любила деньги — он снабжал ее драгоценностями, она жаждала почестей и уважения — он выхлопотал для нее у императора, своего дяди Юстина, высокое достоинство патрицианки. Скоро он захотел жениться на ней во что бы то ни стало. Добрый император Юстин легко согласился на просьбу любимого племянника — он ведь и сам был родом из иллирийских крестьян и в молодости пришел в столицу наниматься в солдаты. Тогда все его достояние составляли козий тулуп и запас сухарей. Рассказывают, что Юстин был первым императором, так и не выучившимся грамоте. Для подписания государственных документов ему изготовили деревянную дощечку с прорезями букв. Племянник же его Юстиниан, будучи еще молодым человеком, стал заправлять всеми государственными делами. Злые языки сравнивали престарелого Юстина с вьючным ослом, который идет туда, куда ведут. Жена его также была из простых, но, стремясь соответствовать нежданно обретенному статусу, сменила имя Луппициана на Евфимия и всемерно демонстрировала «аристократизм», возмущаясь, что женщина, подобная Феодоре, может ей наследовать. К счастью, Евфимия умерла как раз вовремя, в 523 году. И Юстин тут же отменил закон, который не позволял высшим сановникам жениться на женщинах рабского состояния, служанках, актрисах или куртизанках.
