Nemanjina nenadana abdikacija i potiskivanje najstarijeg njegova sina sa velikožupanskog prestola nisu mogli proći bez krize u zemlji. Vukan se osećao uvređenim. Sablažnjiva scena bratske borbe oko vizantiskog prestola imala je svog odjeka i u srpskim zemljama. Vukan, računajući sa još nesmirenim separatističkim strujama u Zeti i sa katoličkim elementom u njoj, koji je teško podnosio pretežni uticaj pravoslavlja u Nemanjinoj državi, dolazi na misao da iskoristi to suparništvo. Neposredan povod za to dao mu je napadaj mađarskog princa Andrije na humsku zemlju. Ovaj je od brata Emerika oteo 1197. herceštvo Dalmacije i Hrvatske i već je s ranog proleća naredne godine napao Hum. Dajući izvestan poklon manastiru Sv. Krševina u Zadru, 6. maja 1198. god., Andrija pominje svoju pobedu "kako u Humu, tako i u Raškoj". U žitiji svog oca Stevan, koji priča kako se odazvao njegovu pozivu da pomogne zidanje Hilandara, kazuje, kako je tom prilikom, dakle 1198./9., uzdajući se u Hrista i njegove molitve, bio bez straha od onih koji su ga napadali, niti se bojao "šetanija inoplemenika varvara". Vukan je s Andrijom sklopio savez protiv brata s namerom, da njegovom pomoću dođe na srpski presto. U leto 1198. god. Andrija se sukobio ponovo s bratom Emerikom i izazvao s toga protiv sebe papino prokletstvo. U Andrijinom slučaju Vukan je našao neposredan primer više za svoje držanje prema Stevanu.

Da obezbedi pobedu svojoj stvari Vukan se te godine bio obratio i papi moleći ga da u njegovu zemlju uputi svoje legate i pojača nadzor i uticaj zapadne crkve. 8. januara 1199. papa se odazvao toj molbi i uputio je u Zetu dva svoja poslanika. Ali šaljući ih papa je svoju preporuku za njih uputio u isti mah i velikom županu Stevanu i ženama obojice braće. Papa, prema tom, nije tim aktom pokazao naročito isticanje Vukana mimo vladajućeg brata; on je samo rado prihvatio priliku da pojača uticaj Rima u tim oblastima gde je pravoslavlje počelo da uzima maha. Vukan, da bi stekao papino poverenje, smatra i prikazuje dolazak legata kao naročitu sreću za svoju zemlju i daje im punu slobodu rada. U isti mah on obaveštava papu, kako je u njegovom susedstvu zlo stanje. "U zemlji mađarskog kralja, t.j. u Bosni", piše on, jeres je uhvatila maha, jer je sam ban Kulin sa ženom i sestrom, udovicom kneza Miroslava, i sa mnogim srodnicima i sa više od 10.000 duša prešao u nju. Vukan ne kaže koja je to jeres, ali je verovatno da misli na bogumilstvo. Mađarski kralj naterao ih je, da se upute papi i da tamo prikažu svoje verovanje, ali su se oni, kazuje Vukan, vratili sa izmišljenim pismima, kao da im je to papa odobrio. S toga on sad moli papu, da savetuje mađarskom kralju, neka ih "istrebi iz svoje države kao kukolj iz šenice".

Ali sve te dostave nisu mogle odlučiti papu da istupi protiv Stevana. A sam Stevan držao se vrlo vešto. I on je, iz straha od katoličkog saveza, predusretljivo primio oba papina legata i u svom pismu papi, kao "svom duhovnom ocu", poručivao, da će uputiti svoje posebno poslanstvo u Rim. Ono je doista i došlo, i to sa naročitom molbom Stevanovom, da mu papa pošalje kraljevsku krunu. U papi, Stevan se nadao dobiti zaštitu od napadaja mađarskog suseda i svoga brata. Misli se, da ga je težnja da dokaže svoj raskid s Vizantijom opredelila, i da otera i svoju ženu, grčku princezu Jevdokiju, navodeći, inače, kao razlog za taj postupak njenu šugu i, kako se pričalo u Carigradu, još i neverstvo. Mi, međutim, držimo da to neće biti. Stevan je Jevdokiju oterao golu, samo u košulji, očevidno ljut radi njenih postupaka; tolika bezobzirnost može se tumačiti jedino velikom ličnom razdraženošću. Sami Grci, koji govore o tom događaju, nisu mu nikako pridavali političke motive.

Papa Inoćentije III, koji je pred očima imao samo crkvene interese, bio bi pristao da Stevanu pošalje krunu, samo da bi pridobio jednog šizmatičkog poglavara više. Ali je mađarski kralj odlučno ustao protiv te namere. To je čak i pospešilo njegovu odluku, da napane Stevana. U savezu sa Vukanom prodrli su Mađari 1202. god. u Srbiju i pokorili je. Vukan je postao veliki župan, dobio je raške zemlje i nišku oblast, a Emerik uze za se titulu srpskog kralja i oblast istočno od Morave. Vukan je, tako, postao mađarski vazal, kao što je bio i bosanski ban Kulin. Stevan sam priča, kako je tom prilikom Srbija bila opustošena, a on se našao van otadžbine. Izgleda, da se sklonio u Bugarsku, prijateljima svoga oca. Između Bugara i Mađara dođe brzo, još 1203. god., do sukoba radi granica u istočnoj Srbiji. Kalojovan ili Jovanica, bugarski vladar toga vremena, srčan i svirep, osta pobeditelj; Mađari moradoše da se povuku iz Braničeva, a Vukan iz niškog kraja. Stevan se, posle te bugarske pobede, vratio u Srbiju, na svoj presto, a Vukan se povukao u Zetu.

I bosanski ban Kulin nalazio se u sličnoj opasnosti. Vukanova dostava i tužba spljetskog nadbiskupa, da je Kulin dao utočište prognatim jereticima iz Spljeta i Trogira, potaknu energičnog papu Inoćentija III da upozori pismom kralja Emerika na ponašanje Kulinovo i da ga pozove da tome učini kraj. Bosanski ban, pozvan na odgovornost, izbegao je opasnosti samo tako, što se napravio da ne razume u čemu bi bila jeres njegove zemlje i tražeći tobože pouke. Papin legat za Balkan, Ivan de Kazemaris, došao je na to u Bosnu i 8. aprila 1203. na Bolinom Polju primio svečano i obavezno odricanje Bosanaca od izvesnih verskih običaja, koje su dotle držali. Predstavnici Bosne, s istim legatom, otišli su potom mađarskom kralju i ponovili pred njim svoje odluke i položili zakletvu. Tom aktu prisustvovao je i Kulinov sin nepoznata imena. Tako se Bosna spasla jedne bede, koja joj je, u doba tadašnje mađarske agresivnosti, mogla doneti velikih neprilika.