Но противостояние не ограничивалось риторикой и внешними проявлениями. Вскоре эти государства-преемники уже располагали грозными армиями. Умелое ведение сельского хозяйства и торговли позволяло им процветать и копить необходимые ресурсы. Кроме того, в эмиграции эти византийцы не утратили способности поглощать постоянные волны миграции народов, вынужденных покидать свои земли. В первой половине XIII века и христианский, и мусульманский миры были охвачены страхом перед монголами, чья империя стремительно расширялась на запад. К 1241 году эти быстрые конные воины уже были на границе Венгрии, где сокрушили коалицию латинян, которая попыталась преградить им путь. Спустя два года то же самое произошло с турками-сельджуками Малой Азии. Султан Коньи (Икониона) сумел уцелеть, но отныне он должен был платить монгольскому хану ежегодную дань. Другие кочевые племена под натиском монголов бежали. В 1237 году группа половцев перешла Дунай и Балканские горы и укрылась в Македонии, разорив по пути земли болгар. Никейские византийцы, не имевшие общей границы с монголами, сумели обратить ситуацию в свою пользу. Они предложили половцам переселиться в долину Меандра в Малой Азии, и те стали важной частью армии Никейской империи. Но не только степные народы вроде половцев служили наемниками у правителей Никеи и Эпира. Как и до 1204 года, в их армиях было много латинян. Византийцы прекрасно понимали, что выходец из Нормандии или Ломбардии не отождествляет себя с фламандскими императорами и их венецианскими союзниками, которые правили Константинополем, а потому готов верно служить за хорошую плату. И так и происходило.
Благодаря этим процессам, с 1220-х годов возвращение имперской столицы стало казаться вполне достижимой целью. К тому же в 1216 году латинский император Генрих умер, а его преемники правили недолго и неэффективно. Латинские территории за пределами столицы резко сократились, и власть в Константинополе держалась только благодаря венецианцам, которые обороняли город и снабжали его с моря. Но, хотя стало очевидно, что рано или поздно Латинская империя рухнет, было не ясно, какой из двух соперничающих византийских императоров положит ей конец. Между Артой и Никеей началась словесная война. В Никее утверждали, что император в Арте фальшивый, потому что был коронован всего лишь архиепископом. Придворные в Арте отвечали на это, что коронация Феодора Ласкариса была недействительна, потому что ее провел так называемый патриарх, который был к тому же архиепископом Никейским. Этот спор мог длиться еще долго, но последовавшие события сделали его ненужным. В 1230 году император Эпира поссорился с болгарским царем Иваном Асенем II. Его опрометчивое вторжение в Болгарию завершилось поражением и захватом в плен в битве при селе Клокотница, а также потерей большей части территории. В 1241 году правитель Эпира отрекся от императорского титула и ограничился тем, что стал именоваться
В последний год своей жизни, во время военного похода во Фракию император Никеи Иоанн III узнал, что один из его молодых подданных мог вести тайные переговоры с болгарским царем и правителем Эпира. Император был тем более встревожен этим известием, что речь шла о Михаиле Палеологе, который вырос во дворце и которого Иоанн воспитывал как собственного сына. Беда была в том, что Михаил обладал всеми качествами, необходимыми для потенциального узурпатора. Его семья, покинувшая Константинополь после захвата латинянами, состояла в брачном родстве с Комнинами и Ангелами, так что Михаил мог притязать на престол по праву рождения. Он даже выглядел как император и, хотя ему не было 30, успел проявить себя как умелый управитель, когда Иоанн назначил его стратигом недавно завоеванных городов Серре и Мельник. Он также был хорошим воином, и его любили солдаты, в том числе латинские наемники, без которых не обходился ни один захват власти. Палеолога схватили и привлекли к императорскому суду, но показания с чужих слов против него оказались сомнительными, и он был оправдан. Чтобы показать, что не держит на него зла, Иоанн отдал замуж за Палеолога свою внучатую племянницу Феодору и назначил его командовать латинскими наемниками.