Nell'anno 1189 i cumani dichiarano guerra a Bisanzio. Come reazione il Basileus ordina al conquistatore di Kotais, Panagiotes Comneno, di prendere Tbilisi, una grande città Cumana, appena arrivato nei pressi di Tbilisi,il generale viene a sapere da fidati informatori che in città si trova il Khan cumano in persona insieme a circa 1500 soldati, e che fuori dalle mura c'è un altro esercito nemico altrettanto numeroso. Panagiotes, ricevuti i rapporti degli informatori decide di assediare la città, ma di non assaltarla in nessum modo, aspettanto che siano i nemici a fare la prima mossa. Dopo qualche mese d'assedio i cumani, forti anche dell'esercito accampato non lontano dalla città, tentano una sortita, Panagiotes si ritira ritenendo che se avesse combattuto in quel momento avrebbe perso troppi uomini. Tre anni dopo il generale bizantino ritorna nella zona e stavolta cerca di distruggere l'esercito situato nei pressi della città, tuttavia la natura montuosa dei luoghi rende proibitivo uno scontro diretto e quindi si viene a creare una situazione di stallo. Nel frattempo poco più a sud veniva occupato il castello ribelle di Kelat,e nel Mar Nero la flotta otteneva vittorie su vittorie e bloccava sistematicamente i porti cumani.
In Italia le cose procedevano veramente bene. Nel 1190 caddero sotto il dominio bizantino Pisa e Lugano. La prima venne occupata in seguito a una sortita fallita dei milanesi, la seconda invece fu "conquistata" da Simonis Comneno una bellissima principessa(10/10). Simonis infatti si innamorò di Giangaleazzo di Lugano e lo sedusse, portandolo sotto la bandiera romana.
Nel 1192 sbarca nei pressi di Pisa un'armata aragonese e assedia la città, inutile dire che nel tentato assalto tutti i nemici morirono.
L'anno seguente Ermanes di Efeso salpa da Reggio con 1600 uomini e sbarca in Sicilia, con l'intenzione di farla tornare sotto il dominio bizantino. In un solo anno vengono prese Sirausa e Palermo, assicurando così a Bisanzio il controllo dell'isola. Ora i siciliani non potevano neanche definirsi tali.
Molto più a nord Giangaleazzo partiva con un piccolo esercito da Lugano alla volta di Innsbruck, fermamente deciso a conquistarla.
Nel 1195 finalmente si poteva dire che l'impero cotrollava tutta l'Anatolia, infatti i crociati cedettero la fortezza all'imperatore in cambio di ben 16000 fiorini.
Una grande sfida però attendeva il Basileus; nel 1196 venne indetta una Jihad contro Costantinopoli, le più grandi armate dell'Islam avrebbero assediato la Città. Alla guerra santa aderirono subito i mori, gli egiziani e i siriani. Dopo tanto tempo l'impero si sentiva minacciato.