Roman, sin nekadašnjeg namesnika današnje Srbije, Konstantina Diogena, beše, čudnim sticajem prilika 1067., postao car. God. 1071. izgubio je jednu bitku i carstvo. U Carigradu, po običaju, počeše strasne spletke i borbe oko prestola. Roman je u Maloj Aziji uzalud pokušao da se održi; ali je tu, na očigled Turaka, koji su sve više uzimali maha, otkrio unutrašnje borbe Vizantije. Sem Turaka, Carevini se javiše neprijatelji i s drugih strana. Južna Italija, pod vođstvom Normana, sasvim se oslobodi vizantiske vlasti. Ove meteže i borbe iskoristiše, među ostalima, i maćedonski Sloveni, čiji se borbeni duh ne beše smirio ni posle toliko skupih iskustava. Možda je bilo kakva potsticaja za to od ljudi cara Romana. Maćedonski boljari, većinom iz okoline Skoplja, pod Đorđom Vojtehom, čije ime ne kazuje slovensko poreklo, digoše pravi ustanak. Da u borbama ne bi ostali osamljeni, oni se obratiše za pomoć knezu Mihajlu u Zeti. Sigurno je bilo sećanja na srodničke veze između Samuila i Vladimira, odnosno na zajednički rad maćedonskih i zetskih poglavara. I ustanak Vojislavljev, sasvim verovatno, ne pada slučajno kad i akcija Petra Deljana. Mihajlo prihvati njihovu ponudu i dade im kao poglavicu svoga sina Bodina, 1073. god. Sa Konstantinom Bodinom Mihajlo je poslao vojvodu Petrila i vrlo mali broj vojske, svega 300 ljudi. Oprezan, Mihajlo kao da nije hteo da ulazi u veliku avanturu i hteo je samo da održi veze s pokretom i da osmotri opštu situaciju. U Prizrenu Bodina proglasiše, prema tradiciji koja je još bila živa za "bugarskog" cara, i po poslednjem bugarskom caru Petru on dobi novo ime Petar. Skopljanski namesnik, koji pokuša da uguši pokret, bi poražen i zarobljen. Na to se maćedonska vojska, nedovoljno mudra, i željna da pokret što više teritorijalno proširi, podeli na dvoje: jedna pođe prema Nišu, s Bodinom kao vođom, a druga u južnu Maćedoniju. I Mihajlo, pomagan od Hrvata, napade na dračku oblast i vizantiske gradove u Dalmaciji, verujući posle prvih uspeha, da je pokret na dobru putu. Međutim, južni deo maćedonske vojske, koji beše bez napora uzeo Ohrid i Devol, nastrada pod gradom Kosturom. Tamo se beše prikupila ne samo vizantiska vojska, nego i neki bugarski i maćedonski velikaši koji su bili protiv ustanka. Suzbivši Petrila, Vizantinci se obrnuše protiv Bodina, uz koga behu pristali svi krajevi od Srema do Vidina. Kad Vizantinci uzeše Skoplje Bodin se, u zimu, po snegu, uputi iz Niša prema Zeti. Kod Pauna, na Kosovu, stigoše ga Grci, potukoše ga i zarobiše. Tako je skrhan i ovaj maćedonski ustanak. Kao zarobljenika odvedoše Bodina u Carigrad, gde ga zatvoriše u manastiru Sv. Srđa i Vakha. Kad je Isak Komnen bio poslat u Siriju, upućen bi tamo, u Antiohiju, i mladi Bodin. Odatle se spasao i vratio u otadžbinu pomoću mletačkih brodara, koje za to beše najmio njegov otac.

Kad je skršen maćedonski ustanak, Vizantija odluči, da kazni i Zećane i Hrvate. Drački namesnik, Nićifor Brienije, dobi naredbu za napadaj. Kratki izveštaj njegova sina kaže, da je on pobedio zetskog neprijatelja, da je uzeo taoce i da je ostavio posade u važnijim mestima, naročito dalmatinskim, koje je opet povratio romejskoj vlasti. Karakteristična je njegova opreznost, za veću sigurnost vojske, da je dao prokrčiti klance i puteve, kako ne bi prošao u toj gorovitoj zemlji kao njegov pretšasnik. Znamo, da je ovom prilikom potpuno uništena Prespa i opljačkan hram S. Ahilija. Dukljaninova Hronika dodaje još, da je u ovim borbama Mihajlo pogubio sve sinove sem zarobljenog Bodina. Borba je završena 1074. god.

U Rimu je, u ovo vreme, bio na čelu crkve kao papa moćni Grgur VII, jedna od najistaknutijih i najautoritativnijih ličnosti u celoj historiji papa. Kao predstavnik božije moći on je na zemlji hteo papskoj vlasti da stvori ne samo moralni, nego – stvarni fizički prestiž. On hoće papsku moć da naturi kao državnu; hoće da bude darodavac kruna; glavni regulator svetske politike u religioznom zamahu. On 1076. god. dovodi do prestola hrvatskog kralja Zvonimira, ali kao vazala papske kurije. Izgubivši poverenje kod Vizantije, knez Mihajlo je morao tražiti naslona na nekoj drugoj strani. Prirodno je, da ga je potražio kod tada silnog pape Grgura, koji mu je od glavnih evropskih sila bio najbliži. Verovatno je delovao i primer hrvatskog kralja. Papa nije imao nikakva razloga, da Mihajlovu ponudu ne primi. U jednom pismu od 9. januara 1078. Mihajlo se naziva kraljem. Prema tome, on je tu titulu dobio po svoj prilici tokom 1077. god. Papa je, primanjem Mihajla, hteo očevidno da pojača svoj uticaj na istočnoj strani Jadranskog Mora, odnosno da povrati poziciju izgubljenu 732. godine. Vrlo je verovatno, da je papa i od Mihajla tražio da prizna njegovu vrhovnu vlast, po svom osveštanom načelu. Mihajlo je to priznao isto kao i Zvonimir, bez ikakva uštrba po politički značaj svoje države. Naprotiv. Ona je tim samo dobila; imala je sad formalno priznanje sa najkompetentnijeg mesta u Evropi. Vredi zabeležiti, da je tih godina, 1076. god., i treća slovenska država, Poljska, dobila "kraljevstvo" od Grgura VII.

Mihajlo je želeo, da u svojoj državi dobije i posebnu arhiepiskopiju kao versku centralu. O tom je i pisao papi Grguru. Katolici njegova područja, – a i on sam beše katoličke vere, – behu pod vlašću dubrovačke episkopije, koju nedavno behu potčinili spljetskoj arhiepiskopiji. Razumljivo je po tom, što Mihailo nije rado gledao, da njegovi podanici imaju svog verskog poglavicu u tuđoj državi. Ali on nije dočekao da mu se ta želja ispuni. Tek je za vreme vlade njegova sina Bodina, 8. januara 1089. god., barska episkopija dobila dugo željeno unapređenje.