Kralj Milutin je naročito sablažnjavao savremeni svet svojim postupcima prema ženama. U tom pogledu za nj nije bilo nikakvih prepreka ni obzira. Svoju prvu ženu, tesalsku princezu, koja mu je rodila sina Konstantina, vratio je prosto kući. Oženio se drugi put svojom prijom, sestrom svoje snahe Katarine, Dragutinove žene, Jelisavetom, koju je zaveo kao kaluđericu. Od nje je dobio kćer, kojoj je dao čudno ime Carica. I nju je oterao posle kratkog vremena i već 1284. god. venčao se sa Anom, ćerkom bugarskog cara Đorđa Terterija. Danas ne znamo, da li je ovde bila po sredi neka strast ili kakav politički račun. Đorđe Terterije, čiju su zemlju Tatari plenili nekoliko puta i čiju je vrhovnu vlast on priznao 1285. god., nije u ovaj mah bio neki značajniji politički činilac. Terterijeva se politika sastojala u to vreme u tom, da traži sporazum na sve strane; možda je on gledao da pridobije Milutina ovom bračnom vezom, iz koje je rođen Stefan Dečanski.

U braničevskoj oblasti behu se osilila dva bugarska velikaša, braća Drman i Kudelin. U Ždrelu na Mlavi, u današnjoj gornječkoj klisuri, behu se oni utvrdili, odmetnuli od svake vlasti i uznemiravahu i srpsko i mađarsko susedstvo. U njihovoj vojsci nalažahu se kao polupljačkaši a polunajamnici ljudi raznih narodnosti, a ponajviše Bugari, Tatari i Kumanci. Ozlojeđeni na njih Mađari su početkom 1285. god. uputili protiv njih jednu vojsku da ih kazni. Njihovom primeru sledovali su malo kasnije i Srbi. Kralj Dragutin, kao neposredni sused, pokušao je sam da ih kazni, ali im nije mogao učiniti ništa, jer su se bili odlično utvrdili u inače teško prohodnom klancu. Dragutin je, po svoj prilici pretrpeo poraz, jer Drman i Kudelin pređoše odmah u napadaj protiv njega i zauzeše mu izvesne krajeve. Dragutin pozva Milutina na dogovor u Mačkovce na Moravi i zamoli ga za pomoć. Milutin se odazvao. Ujedinjena srpska vojska ušla je potom u Braničevo, potukla i proterala pljačkaše i njihove gospodare, i zavladala čitavom oblašću. Braničevo je predato Dragutinu; tada je prvi put došlo pod srpsku vlast i ostalo u njoj celo vreme posle toga.

Posle ovog poraza Drmana i Kudelina rešio se vidinski knez Šišman, koji je možda imao nekih veza s njima ili polagao pravo na njihovo područje, da se obračuna sa Srbima. Iznenada, ne zna se tačno koje godine, prodro je on sve do Hvosna, a nameravao je, među ostalima, da opljačka pećsku arhiepiskopiju. Ali tu je pretrpeo poraz od srpske vojske, koja je dohrlila odnekud s juga, i morao se naglo povlačiti. Srbi su se dali u poteru za njim i gonili su ga sve do Vidina. Šišman se s mukom prebacio preko Dunava, dok su Srbi zauzeli vidinski grad. Sa leve obale reke poslao je pobeđeni knez ljude, da mole kralja za pregovore. Mir je sklopljen na osnovi: da Šišman prizna vrhovnu vlast srpskog kralja, a kao jemstvo imala je biti Šišmanova ženidba sa kćerju jednog srpskog velmože. Doista, Šišman je doskora uzeo kćer velikog župana Dragoša, a docnije njegov sin Mihajlo Milutinovu kćer Anu, koju docnije pisci zovu narodski i Nedom.

Ovo ratovanje Srba po Braničevu i vidinskoj oblasti dovede ih u sukob s tatarskim hanom Nogajem. Nogaj, koji je imao posebnu oblast od područja današnje Rumunije, od Železnih Vrata i Dunava, do iza Krima, u izvesnoj još ne utvrđenoj vezi sa Zlatnom Hordom u Rusiji, bio je moćan gospodar i znatno je uticao na političke prilike u zemljama severnog Balkana. Pred njim je pobegao u Vizantiju bugarski car Terterije i bio zamenjen u vlasti vojvodom Smilcem, kao novim bugarskim carem pod vrhovnom vlašću Nogajevom. U susednim ruskim oblastima njegova se reč slušala bez pogovora. Vizantiski car Mihajlo Paleolog dao mu je još 1273. god. svoju jednu kćer za ženu. S toga je, prilikom careva spremanja protiv Srba 1282. god., njegovoj vojsci došao u pomoć i jedan veći tatarski odred. Silni Nogaj, koji je imao ranije sukoba i sa Poljacima i sa Mađarima, bio je spreman da napane i Srbe, jer je on od Srba osvojena područja, naročito vidinsku oblast, smatrao kao svoju domenu. Za taj napadaj on je već krenuo i vojsku. Milutin, koga su obavestili o Nogajevoj snazi, uplaši se i ponudi pregovore. Vrlo je verovatno, da je kralj tom prilikom dao obaveze, da ne misli preduzimati nikakve dalje akcije u tim oblastima. Kao zalogu za svoju dobru volju uputio je Nogaju kao taoca svog sina Stevana sa nekoliko druge dece iz vlasteoskih kuća. Oni su ostali među Tatarima sve do Nogajeva sloma i pogibije, kad je došlo i do raspadanja njegove države. Hronologija tih događaja još nije utvrđena; datumi se razilaze u krupnoj meri.

Kad su nastale među Tatarima međusobne borbe, odlučio se bugarski car Smilec da se oslobodi njihove vrhovne vlasti. Da to postigne on se obratio za pomoć kralju Milutinu. Sporazum između Srba i Bugara imala je da utvrdi bračna veza između Milutinova sina Stevana i Smiljčeve kćeri Todore. Ali se Smilac nije mogao održati. Njega je srušio s vlasti Terterijev sin Svetoslav u zajednici s Nogajevim sinom Čekom (Čakom), koga je posle Svetoslav dao ubiti. Šta se dogodilo posle sa Smilcem nije poznato; sigurno je samo to, da se Milutin nije radi njega odlučivao ni na kakve oštrije mere; on je u to vreme bio zauzet krupnim pregovorima sa Vizantijom.