En ese momento, Irene ya estaba casada con Andrónico Contostéfano, quien, según Nicetas Coniata, era un pariente lejano de su madre Eufrósine.
Andrónico Contostéfano murió alrededor de 1196, habiéndose retirado recientemente a un monasterio.
Alrededor de 1198, el emperador decidió casar a la viuda Irene con el sebastocrátor Alejo Paleólogo.
Alejo III, que no tenía hijos, planeó a través de este matrimonio tener un heredero al trono en la persona de su nuevo yerno.
En ese momento, sin embargo, el sebastocrátor ya estaba casado, por lo que el emperador lo obligó a divorciarse de su primera esposa.