Az újabb tatár betörésekről szóló, szünni nem akaró hirek 1258-ban, ép a stiriai bonyodalmak közepette, pozitivebb formát kezdtek ölteni. Habár Batu khán 1255-ben, 48 éves korában meghalt, azért a kipcsaki mongol birodalom utóda, Nogaj alatt, erősen tartotta magát és különösen Orsozországot keményen kezében tartván, a többi európai országokat is állandóan rettegésben tartotta.

1258. őszén tatár küldöttség jelent meg IV. Béla előtt Nogaj khán üzenetével, hogy útóbbi vele szövetségre kiván lépni a következő feltételek alatt: a) vagy Béla fia vegy el az ő leányát, vagy az ő fiának adja nőül Béla leányainak egyikét; b) Nogaj legközelebb újabb háborút indít az európai keresztények ellen; ez alkalommal Béla fia csatlakozzék hozzá a magyar haderő negyed részével, amiért jutalmul az elfoglalandó tartományok és a szerzett zsákmány egyötöd részét kapja; c) ha Béla e feltételeket elfogadja, úgy a tatár sereg az ő országát megkiméli, ha pedig nem, akkor számoljon a khán rettenetes bosszújával.

IV. Béla ezt az ajánlatot hosszas gondolkozás nélkül a leghatározottabban visszautasította és arról nyomban értesítette a pápát, tőle egyúttal a rettenetes ellenség biztosra vehető újabb betörése ellen segítséget kérvén. Mindenekelőtt azt kivánta, hogy a pápa a magyar egyházi jövedelmek egy ötödrészét engedje át neki a háború költségeire, s azonfelül küldjön neki 1000 kőhajító számszeríjászt (ballistarios) s végül igérje meg, hogy jövőben a magyar püspöki székeket nem fogja idegenekkel betölteni.

IV. Sándor pápa hajlandónak nyilatkozott, hogy Béla összes kivánságait teljesíti, kivéve a számszeríjászokra vonatkozót, miután ilyenek felett állítása szerint ő sem rendelkezett.[1]

1259-ben a tatárok Burundáj vezetése alatt tényleg megindultak nyugat felé, azonban csodálatosképen nem Magyarország felé vették útjokat, hogy IV. Béla visszautsító magatartását megtorolják, hanem Oroszországon át Lengyelországba.

Közeledésük hirére Danilo, a halicsi fejedelem, bár ő mint tudjuk, még Batu idejében a tatárok vazallusává vált, de miután utóbb 1255-ben a pápától királyi koronát is nyert s így most már inkább a nyugat, mint kelet felé hajlott, gyöngének érezvén magát arra, hogy a tatároknak ellentálljon, Magyarországba menekült IV. Bélához. Ellenben fia Leo és öccse Vaszilko meghódoltak a közelgő Burundájnak, akinek parancsára maguk rombolták le városaik falait s azután hadaikkal hozzácsatlakoztak a tatárok seregéhez s azzal együtt 1259. november végén elindultak Lengyelország ellen.

[1] IV. Sándor pápa 1259. október 14-én kelt, IV. Bélához intézett levele. (Raynald, Annales Eccl. az 1259. évhez n. 33. ep. 191.)