W tym czasie sam zresztą popadł w zależność od Tatarów i był zmuszony wysłać swego syna Stefana Deczańskiego na dwór Nogaja.
Pomimo uzależnienia od Serbii, na które wskazuje również późniejszy ślub syna Szyszmana Michała z córką Milutina Anną Nedą, dzięki obecności Tatarów Szyszman mógł prowadzić stosunkowo niezależną politykę w stosunku do Wołoszczyzny, a zwłaszcza do Bułgarii. Po zamordowaniu przez Toktu chana Nogaja (1299) i rozpadzie jego ordy, udzielił w latach 1301-1302 schronienia niektórym z krewnych Nogaja, między innymi wnukowi chana Kara-Kesekowi, który zbiegł do Widynia z liczącym 3 tysiące jazdy oddziałem i pozostawał tam jeszcze w 1325 rokuI. Vásáry, Cumans and Tatars, s. 88. W przeciwieństwie do Andrejewa, Fine uważa, że śmierć Nogaja zwiększyła wpływy serbskie w Widyniu.