Ее положение мало изменилось и после смерти Феодора II Ласкаря, захвата престола Михаилом Палеологом и последующем взятии Константинополя. Об этом последнем событии следует сказать несколько слов. В 1261 году брат нового императора Иоанн должен был начать войну против Эпирского деспотата, и ему в помощь был послан отряд под командованием известного полководца кесаря Алексея Стратигопула. Отряд состоял из небольшого количества греков и девяти сотен турок-сельджуков. Кесарю была дана инструкция по дороге подойти к Константинополю и разведать положение в городе. В конце июля 1261 года отряд подошел к городу, и тут выяснились очень интересные вещи: оказывается, по инициативе представителя Венеции, Градениго, рыцари императора Балдуина и венецианцы погрузились на корабли и отправились в Черное море для захвата города Дафнусия. Знали бы они, чем обернется этот поход! В городе оставался только небольшой гарнизон, и Алексея Стратигопула легко убедили в возможности быстрого и легкого захвата города. Штурм был назначен на 25 июля 1261 года.
Пятьдесят солдат под руководством местного грека Кутрыцака через старый водосток ночью проникли в город. Они без шума перебили сонную стражу, разобрали завалы у ворот и сбили с них засовы. Утром конница Стратигопула вошла в город через открытые ворота, а местное население открыто ее поддержало. Среди латинян началась паника, которая усилилась, когда кесарь велел поджечь часть города, в том числе и венецианский квартал. Турки начали грабить город, но Стратегопул сдерживал их и не пускал в центр города. Император Балдуин II и не думал о сопротивлении: бросив даже свои регалии, корону и меч, он сел на венецианский корабль и отплыл на Эвбею. Кто из латинян смог добраться до кораблей, тот избежал смерти, а остальные были безжалостно перебиты. Император Михаил Палеолог узнал об этом только через несколько дней, когда его сестра Евлогия ночью разбудила его словами:
"Царь, ты взял Константинополь! Христос даровал его тебе!"
Но Михаил и весь двор не сразу поверили в это.
Анна вместе со всем двором переехала в Константинополь, но оставалась такой же пленницей. Она, конечно, сохраняла положение и образ жизни, которые приличествовали императрице, но пользовалась своими преимуществами крайне скромно. Придворный летописец писал об Анне:
"Она украшала свое существование красотой своих добродетелей, и чистота ее нравов еще более оттеняла сияющую прелесть ее лица".
Анна была красива, ей было около тридцати лет, и нет ничего удивительного в том, что новый император обратил на нее свое внимание и сильно ею увлекся. К тому же в обычае почти всех византийских узурпаторов было брать себе в жены или любовницы вдов своих предшественников, чтобы таким образом узаконить свой захват власти. Но тут он встретил достойного соперника. Анна презрительно отвергла его поползновения и сказала, что она, вдова императора и дочь Фридриха II, не может унизиться и стать любовницей человека, который был ее подданным.
После нескольких неудачных попыток Михаил понял, что есть только один способ завоевать Анну: жениться на ней. Но Михаил уже был женат на Феодоре, красивой и очень добропорядочной женщине из благородной семьи, которая к тому же родила ему троих сыновей. Имея такую жену, было очень трудно найти достойный предлог для развода, а об ее добровольном согласии на развод нечего было и мечтать. Тогда Михаил решил подключить к этому вопросу политику. На Государственном совете он стал перечислять опасности, угрожающие недавно восстановленной Империи. Он перечислил государства и правителей, которые вошли в союз для возврата Константинополя. Среди них был и Сицилийский король Манфред. Если бы удалось его вывести из союза, это значительно облегчило бы положение Византии. Для этого есть один способ: надо Михаилу развестись с Феодорой и жениться на сестре Манфреда Анне. Все это он готов сделать исключительно для блага государства!
Но Михаил наткнулся на отчаянное сопротивление своей жены. Феодора привлекла на свою сторону патриарха Арсения, который возмутился происками императора, стал угрожать ему отлучением от церкви, если он будет упорствовать в своих стремлениях, и, как пишет летописец,
"разбил его убедительные доводы так же легко, как рвут паутину".
Императору пришлось отступить в этом вопросе, но с этих пор началась вражда между Михаилом Палеологом и патриархом Арсением.
Вскоре, однако, подвернулся повод использовать Анну в политических целях: в 1262 году Эпирский деспот захватил в плен славного Алексея Стратигопула и отправил его в качестве трофея к Манфреду. Михаил не мог допустить, чтобы освободитель Константинополя томился в плену, народ бы его не понял, и вступил в переговоры с Манфредом об обмене знатного пленника на императрицу Анну. В 1263 году обмен состоялся, но ожидаемого улучшения отношений с Гогенштауфенами не произошло.
Анна же вернулась на родину, но и здесь ее ожидали тяжелые испытания. В 1266 году в битве при Беневенто погиб Манфред, а его жена и дети были брошены в тюрьму. Анну почему-то сочли не очень опасной и оставили на свободе. В 1269 году она уехала в Испанию к своей племяннице Констанции, которая была женой инфанта, дона Педро Арагонского. Здесь Анна, наконец, нашла мир и покой. Она приняла пострижение в монастыре Святой Варвары в Валенсии. В дар монастырю она принесла чудотворный образ его святой покровительницы и обломок скалы, из которой забила вода для крещения Св. Варвары - это было все, что она вывезла с Востока. Здесь они и умерла почти в полной безвестности около 1313 года. В Валенсии еще в начале XX века в маленькой церкви Иоанна больничного в часовне Святой Варвары можно было видеть деревянный гроб с надписью:
"Здесь лежит тело донны Констанции, августейшей императрицы Греческой".