Nogaj nie chciał sam decydować o najeździe na ziemie księcia polskiego Leszka Czarnego, dlatego postanowił działać wspólnie z Telebogą, mimo że obaj Mongołowie nie darzyli się sympatią.
Pomimo niechęci współdziałali ze sobą uzgadniając wszelkie posunięcia polityczne i militarne. Wojska mongolskie po opuszczeniu Węgier i zaplanowaniu kolejnej wyprawy, znalazły leże w pobliżu ziem polskich: armia Telebogi w południowo-wschodnich rejonach Księstwa Halicko-Wołyńskiego armia Nogaja w okolicach między Dniestrem a Seretem. Najważniejszym celem planowanej wyprawy miała być grabież i złupienie Polski, a dokładniej Małopolski i ziemi sandomierskiej. Celem politycznym miało być zapewne osłabienie gospodarcze i militarne państwa księcia Leszka Czarnego, który w tamtych czasach wyrastał na najważniejszego sojusznika Węgier, rywala Złotej Ordy. Jednak cel polityczny najazdu był celem drugorzędnym. Plan wyprawy był prosty i podobny do poprzedniego najazdu mongolskiego z przełomu 1259 i 1260. Spośród dwóch armii północna, pod dowództwem Telebogi, miała uderzyć na ziemię sandomierską, południowa – mniejsza liczebne, pod dowództwem Nogaja, miała iść bezpośrednio na Kraków i Małopolskę. Obie armie miały spustoszyć zaatakowane ziemie i spotkać się na północ od Krakowa.