Justinianus, a jövendőbeli császár már harmincadik événél járhatott, amikor megismerte Theodórát. Justinianus: nagyon megszerette Theodórát és elhalmozta ajándékokkal. (Prokopiosz szerint Theodóra rendkívül kapzsi volt). Justinianus rávette nagybátyját, a császárt, hogy nevezze ki Theodórát patríciusnőnek, és megkérte, hogy engedélyezze, hogy házasságot köthessenek. [[I. Justinus bizánci császár|Justinus császár]] hajlott volna az utóbbi kérés teljesítésére, mert ő is nagyon kedvelte Theodórát, de felesége [[Euphemia bizánci császárné|Euphemia Lupicina]] (aki egyébként barbár rabszolgalányként született) mereven ellenezte a házasságot. Arra a törvényre hivatkozva, hogy szenátorok és magas rangú emberek nem vehettek feleségül színésznőket, kurtizánokat és hetérákat. Megoldásképpen ezt a törvényt később Justinus és Justinianus eltörölték.
523-ban meghalt Euphemia császárné, így a házasságot (amit valószínűleg már 514-ben megkötöttek) Justinianus és Theodóra között hivatalosan is elismerte a pátriárka. Prokopiosz szerint JutinianusnakJustinianusnak és Theodórának egy fia és egy lánya született. A fiút Jóannésznek hívták és, a lányuk az édesanyja nevét, a Theodórát kapta.