Po naređenju makedonskog cara Jovana Vladislava dukljanski vladar Vladimir ubijen je u Prespi 1016. godine, a Duklja je pala pod vlast Makedonskog carstva. Jovan Vladislav je poginuo u borbi protiv vizantijske vojske kod Drača 1018. godine. Zatim je vizantijski car Vasilije II (976–1025) uništio Makedonsko carstvo i zauzeo je najveći dio Balkana. Od Bugarske, Makedonije i Srbije formirao je istoimene vizantijske teme (provincije), dok je u Duklji (s Travunijom) i u Zahumlju postavio vazalne vladare. Prema Ljetopisu popa Dukljanina, vladar u Duklji se zvao Dobroslav (lat. Dobroslavus), dok se u vizantijskim izvorima naziva Stefan Vojislav (gr. Στέφανος Βοϊσθλάβος).
Postoji nedoumica oko njegovog identiteta. Pop Dukljanin navodi da je on bio Vladimirov brat od strica Dragimira i da je rođen kao posmrče, jer je Dragimir ubijen 1018. Dukljaninova tvrdnja podrazumijeva da je Dobroslav rođen najkasnije početkom 1019. godine, da je vazalni vladar postao ubrzo po rođenju i da je oko 1040. imao pet odraslih sinova, što je nemoguće. Vjerovatno je rođen sredinom 990-ih. Zbog ovih kontradiktornosti u istoriografiji postoje različita mišljenja o njegovom porijeklu.
Akademik Sima Ćirković ističe da je Vojislav rodonačelnik dukljanske dinastije, ali da nije sigurno da je bio porijeklom iz Duklje, dok akademik Božidar Ferjančić navodi da je Stefan Vojislav zapravo Vladimirov sin. Gotovo svi istoričari smatraju da su Dobroslav i Stefan Vojislav jedna ličnost i da je on pripadnik Vladimirove porodice. Prednost daju imenu Stefan Vojislav, jer se tako naziva u nekoliko vizantijskih hronika iz XI i XII vijeka.
U Ljetopisu se navodi da se školovao u Dubrovniku, koji je tada bio pod vizantijskom vlašću i da se oženio sinovicom makedonskog cara Samuila s kojom je imao pet sinova: Gojislava, Mihaila (Mihalja), Saganeka, Radoslava i Predimira. U kasnijim hronikama se navodi da se njegova žena zvala Neda (Domenica) i da je možda bila unuka, a ne sinovica cara Samuila.
Dubrovački hroničar Jakov Lukarević je početkom XVII vijeka zabilježio da su početkom XI vijeka u Dubrovniku boravili kralj Dalmacije Stefan i njegova žena Margarita, ali nije sigurno da se to odnosi na Stefana Vojislava. Sigurno je da je Vojislav odgajan i obrazovan kao prestolonasljednik i da mu je brak ugovoren sa pripadnicom makedonske vladarske porodice.
U periodu vladavine vizantijskih careva Vasilija II, Konstantina VIII (1025–1028) i Romana III (1028–1034) Vojislav je bio vizantijski saveznik. S vizantijskim činovnicima je obilazio provincije i pomagao im je u upravljanju, ali je, kako navodi pop Dukljanin, potajno organizovao pobunu protiv Vizantije i držao je antivizantijske govore. Za pobunu nije bilo uslova dok je vladao car Vasilije II koji je vizantijski režim učinio popularnim tako što je smanjio poreze, uredio da se oni plaćaju u naturi i uvažavao je lokalne običaje i autonomiju. Tokom nerodnih 1023. i 1024. car je naredio da se porez ne naplaćuje. Konstantin VIII i Roman III su odustali od te politike.
Podigli su poreze i vratili su plaćanje u novcu. Nezadovoljstvo je buknulo kada je na vlast došao car Mihailo IV (1034–1041) čiji je brat Jovan Orfanotrof bio zadužen za državne finansije. Drastično je povećao poreze i naredio je da se plaćaju zlatnim novcem, a u upravi je postavio beskrupulozne činovnike. Režim je bio toliko omražen da je čak i vizantijski hroničar Jovan Skilica za vladu Orfanotrofa naveo da je bila strašna tiranija.
Pop Dukljanin ističe da je narod u Duklji tada žestoko mrzio Grke (činovnike i poreznike), da su narodni predstavnici složno dogovorili podizanje ustanka i da su u toku jednog dana pobili sve grčke velikaše koje su zatekli. Zatim su ustanici pozvali Vojislava i njegovih pet sinova da „preuzmu kraljevstvo i zemlju svojih predaka“. Vojislav je prihvatio i sa sinovima je poveo rat protiv Vizantije 1034-5.
Poslije početnog uspjeha, ustanak je ugušen najkasnije 1036. godine, a Vojislav je zarobljen i odveden u Carigrad. Iako zarobljenik, bio je prvi dukljanski vladar za koga se pouzdano zna da je boravio u Carigradu, što je bilo značajno iskustvo. Tamo je ostao do kraja 1037. ili početka 1038. godine kada je pobjegao u Duklju.
Podigao je drugi ustanak i iz Duklje je protjerao vizantijskog upravnika. Poučen neuspjehom prvog ustanka, odustao je od većih sukoba i vodio je gerilski rat. Hroničar Skilica navodi da se Vojislav utvrdio u „Ilirskim planinama“, a hroničar Jovan Zonara navodi da se Vojislav „s četom skrivao u Ilirskim brdima“ odakle je napadao vizantijsku teritoriju.
Pojam Ilirija se u vizantijskim hronikama u XI i XII vijeku odnosi na Dračku temu. To znači da se Vojislav skrivao u graničnom pojasu između Duklje i Dračke teme, odnosno u planinskim oblastima oko Skadarskog jezera i da je odatle izvodio gerilske akcije. Pogranični gerilski sukob je prerastao u otvoreni rat zbog neobičnog zapleta.
Jovan Orfanotrof je 1039. godine naredio da se zlato, najvjerovatnije porez prikupljen u vizantijskoj Dalmaciji, isporuči caru Mihailu IV u Solunu u kojem je proveo veći dio vladavine. Novac je utovaren na brod koji je tokom plovidbe duž istočnojadranske obale upao u oluju i razbio se „na obalama Ilirije“, odnosno Dračke teme. Sjeverna granica teme je bila oko Bara, a s obzirom na to da je Vojislav prvi došao do razbijenog broda, vjerovatno se brodolom dogodio u barskoj oblasti. Skilica je zapisao da je Vojislav tada zaplijenio 10 kentenarija (κεντηνάρια) zlata. Istoričar Jadran Ferluga navodi da je 1 kentenarij (centenarij) sadržao 10 funti zlata, a da je jedna funta zlata težila 320 g.
Prema toj računici, Vojislav je zaplijenio oko 32 kg zlatnog novca (nomizmi). Prosječna težina nomizme je bila oko 4,55 g zlata tako da je Vojislav zadobio oko 7.200 nomizmi. Britanski numizmatičar Majkl Metkalf navodi da su to bili zlatnici koji su iskovani u vrijeme cara Romana III. U to vrijeme ovo je bilo izuzetno bogatstvo koje je omogućilo Vojislavu da mobiliše i opremi vojsku za borbu protiv carske armije. Sigurno je tim novcem finansirao državni aparat i obezbijedio naklonost vlastele.
Da se radilo o velikoj sumi potvrđuje podatak da je car Mihailo IV poslao pismo Vojislavu i ultimativno zahtijevao da mu vrati zlato, ali je Vojislav ignorisao carev zahtjev. Car je protiv Vojislava poslao vojsku koju je predvodio Georgije Provatas u proljeće 1040. godine. Vizantijski izvori sažeto navode da je Vojislav ovu vojsku porazio u „gudurama i jarugama“ i da je cijela uništena, a da se Provatas jedva spasio bjekstom.
Bitku je detaljnije opisao pop Dukljanin, s tim što on kaže da se vizantijski komandant zvao Armenopolos i da je predvodio veliku vojsku konjanika i pješaka. Vjerovatno je to bio jedan od komandanata u vizantijskoj vojsci. Pop Dukljanin navodi da se bitka desila u Zetskoj ravnici (planitiem Zentae) kod Vranja (Vuranie). Vojislav je podijelio vojsku. On i njegov sin Radoslav su bili u zapadnom dijelu, dok su njegovi ostali sinovi s drugim dijelom vojske zauzeli istočni dio ravnice kod Vranja. Kada se pojavila vizantijska vojska Vojislav ih je iznenada napao, a Radoslav je Armenopolosa udario mačem i zbacio ga je s konja. To je izazvalo paniku u vizantijskoj vojsci koja je bježala prema Vranjskoj gori đe je u zasjedi dočekao drugi dio dukljanske vojske. Pop Dukljanin navodi da je „nad Grcima toga dana učinjeno veliko uništavanje i ranjavanje“.
Postavljanje zasjede i uvlačenje brojnijeg neprijatelja u klopku bile su omiljene Vojislavove taktike. Iskustvo iz dva ustanka i gerliskog rata pokazalo mu je da se nadmoćnija vizantijska vojska ne može pobijediti u linijskoj formaciji na otvorenom prostoru, već da je ona ranjiva u iznenadnim i gerilskim sukobima. Stefan Vojislav je drugi ustanak i gerilski rat okončao pobjedom u bici kod Vranja (Zetska bitka), što je bio izuzetan uspjeh.
Dukljanska država s balkanske periferije, koja se prostirala između gornjeg Lima, rijeke Tare, gornje Neretve i Jadranskog mora, pobijedila je moćnu carevinu. Vizantija je morala da se pomiri s gubitkom zlata i kontrole nad Dukljom, a ubrzo se suočila i s većim problemom. U ljeto 1040. godine, takođe zbog velikih poreza i surove vladavine, ustanak je izbio u vizantijskim provincijama od Beograda do Soluna i od Drača do Sofije. Ustanak je vodio Petar Odeljan. Ustanici su zauzeli Drač početkom 1041. godine, što je iskoristio ratoborni Stefan Vojislav. Prema Ljetopisu popa Dukljanina, Vojislavovi sinovi su zauzeli cijelu Dračku oblast do rijeke Vojuše (alb. Vjosë). No, Vizantija je uspjela da uguši ustanak i da obnovi vlast u pobunjenim provincijama u drugoj polovini 1041. godine, tako da se i dukljanska vojska morala povući iz Dračke teme.
Vojislav je nastavio napade na pogranične oblasti Vizantije. Borbu mu je olakšala politička kriza carstva. Car Mihailo IV je umro u decembru 1041. godine, a naslijedio ga je sinovac Mihailo V koji je htio da vlada kao tiranin. Zbačen je s vlasti u državnom udaru aprila 1042. godine.
Nakon kraćeg perioda za novog cara je izabran Konstantin IX Monomah (1042–1055). Među njegovim prvim potezima bio je obračun sa Dukljom. Car je naredio upravniku Dračke teme patrikiju i katepanu Mihailu, sinu logoteta Anastasija, da sakupi vojsku iz dračke i susjednih tema i da zajedno krenu protiv Vojislava. Titulu katepana (κατεπάνω) imali su upravnici glavnih provincija, što znači da je Dračka tema bila glavna vizantijska oblast na zapadnom Balkanu. Patrikije i katepan Mihailo je imao komandni čin glavnog stratega (generala), dok su zapovjednici iz ostalih tema bili hipostratezi (ὑποστρατηγοῖς) odnosno general-potpukovnici.
Skilica navodi da je vizantijska vojska imala oko 60.000, a drugi vizantijski hroničar Kekavmen navodi oko 40.000 vojnika. Na Duklju je krenula impozantna armija. Značajan je zapis Skilice da se pohod protiv Duklje poklopio sa pojavom komete koja je putovala sa istoka na zapad i cijeli mjesec je sijala na nebu. Iz astronomskih proračuna se zna da se kometa pojavila 6. oktobra 1042. godine i zahvaljujući tome dobijeno je precizno datiranje ovog događaja.
Patrikije Mihailo nije imao vojničko iskustvo i izgleda da je bio arogantan i lakomislen. Dukljanska vojska je bila manja, ali vjerovatno dobro opremljena i prekaljena u borbama, a Vojislav je bio vješt komandant sa iskustvom vođenja rata protiv Vizantije.
Vizantijski izvori navode da je Mihailo krenuo prema Vojislavu koji se povlačio preko brdovitog terena kako bi protivnika doveo u klopku. Vizantijski komandanti nijesu naučili lekciju iz poraza u bici kod Vranja. Njihova vojska je išla kroz uske prolaze kojima često nijesu mogla dva konjanika uporedo da prođu. Tako je Vojislav neutralisao brojčanu nadmoć protivnika. Potom, Mihailo se posvetio pljački i uzimanju zarobljenika i nije mislio na odstupnicu. Dok je vizantijska vojska pustošila i pljačkala, Vojislavovi vojnici su joj iza leđa postavili zasjedu.
Nakon što je sakupio veliki plijen i dosta zarobljenika Mihailo je naredio povlačenje istim putem i upao je u Vojislavovu zasjedu. Dukljanska vojska je sa visova napala Vizantince stijenama, kamenjem i strijelama. Skilica navodi da je poginulo oko 40.000 vizantijskih vojnika i čak sedam generala (στρατηγοὶ ἑπτά), dok kod Kekavmena nema procjene broja poginulih. Mnogi istoričari su sumnjali u vjerodostojnost podataka o veličini vizantijske vojske i o broju poginulih. To bi bila opravdana sumnja da je ovo zapisala dukljanska strana.
No, to su zapisi vizantijske (gubitničke) strane. Nije uobičajeno da poražena strana uveličava svoj poraz. Obično je obrnuto, tako da je nesumnjivo vizantijska vojska bila brojna, da je pretrpjela velike gubitke i ponižavajući poraz. Skilica kaže da je krivac „ove velike nesreće za državu Romeja [Vizantiju]“ bio vrhovni zapovjednik Mihailo koji se spasio bjekstvom, a da su preživjeli „davali tužan i suza dostojan prizor onima koji gledaju“. Kekavmen ističe da je Mihailova presudna greška bila što se povlačio istim putem kojim je upao u Duklju. Uz to, Kekavmen navodi da je Mihailo zarobljen.
(Sjutra slijedi II dio)
