Prva crnogorska država, Kraljevstvo Duklja, nastala je na prostoru nekadašnje rimske provincije Prevalitane. Od XI vijeka Duklja se počinje nazivati Zetom, a kasnije Crnom Gorom. Prvom dukljanskom, tj. zetskom/crnogorskom dinastijom, smatraju se Vojislavljevići. Naziv su dobili po knezu Vojislavu, koji je na prijestolju naslijedio Svetog Vladimira. Vojislav se u LJetopisu popa Dukljanina naziva i Dobroslav.
Za vrijeme vladavine kneza Vojislava odigrao se jedan od najznačajnijih događaja iz crnogorske prošlosti. Bila je to Barska ili Tuđemilska bitka, koja se odvijala u noći 6. na 7. oktobar 1042. godine, između vizantijske, tj. grčke i dukljanske vojske. O ovom događaju izvore nalazimo u spisima Jovana Skilice, vizantijskog hroničara iz XI vijeka i u djelu Kraljevstvo Slovena, poznatom kao LJetopis popa Dukljanina.
Slovenske kneževine na Balkanu potpadale su do početka XI vijeka pod vlast Vizantije. Stanovnici nijesu mirovali, već su ustancima nastojali da se oslobode vizantijske uprave. Poslije ustanka makedonskih Slovena koji je ugušen, oko 1035. pobunili su se Dukljani pod vođstvom kneza Vojislava. Poslije početnog uspjeha Vojislav je zarobljen i odveden u Carigrad. Uspio je da pobjegne krajem 1037. ili početkom 1038. godine. Potisnuo je iz Duklje Vizantijskog namjesnika Teofila Erotika.
Poseban gnijev
Vizantiji se Vojislav posebno zamjerio kada je u zimu 1039/1040. godine, sa jednog nasukanog vizantijskog broda, zadržao za sebe zlatni tovar. Vizantijski car je napao Duklju u jesen 1040. godine. Vojsku, predvođenu Georgijem Probatom (ili Provatasom), Vojislav je potpuno razbio. Probat, „stigavši u zemlju i zapavši u gudure, jaruge i besputna mjesta, izgubi cijelu vojsku i sam se jedva spasi“.
U međuvremenu je izbio i ustanak u Makedoniji, koji je predvodio Petar Deljan. Taj ustanak se urušio unutrašnjim sukobima, a 1042. godine na prijesto u Vizantiji dolazi Konstantin IX Monomah. Iste godine on je izdao naređenje o napadu na Duklju. Prikupio je velike snage, a u pomoć je vizantijski car pozvao svoje vazale, kneza Zahumlja, župana Srbije i bana Bosne: „Kad je grčki car čuo što se dogodilo, razbiješnjen velikim bijesom a nesrećan u duši, posla odmah izaslanike sa prilično zlata i srebra da to daju raškom županu i bosanskom banu i knezu Zahumske oblasti, da bi ovi poslali vojsku i narod protiv kralja. Tada župan i ban, pošto sakupe mnoštvo naroda, poruče LJutovidu knezu Zahumske oblasti, da bi ovi poslali vojsku i narod protiv kralja. Tada župan i ban, pošto sakupe mnoštvo naroda, poruče LJutovidu knezu Zahumske oblasti, da sjedini sve mnoštvo i da on sam bude vođa čitavog naroda. I tako bi učinjeno. A car s druge strane sakupivši vojsku mnogo veću nego ranije, pošalje u Drač i naredi nekom Kursiliju, toparhu, koji je u to vrijeme držao Drač i čitavu dračku zemlju, da sakupi sav narod dračke zemlje i da se stavi na čelo čitave vojske, pa da krene da uhvati kralja (Vojislava, prim. D. B. P) i njegove sinove bilo đe ih bude pronašao.“
Taktika dobrog vođe
Kako navodi pop Dukljanin, Kursilije je vojsku, koje je bilo „toliko mnoštvo ljudi da ih je zemlja jedva primila“, prikupio oko Skadra i stigao do Bara. Vojislav se s vojskom nalazio u Crmnici. Pošto je vidio da pred sobom ima višestruko brojčano jačeg neprijatelja, dukljanski vladar pripremio je posebnu taktiku: „Vidite najdraži sinovi, da je velika grčka vojska, a nas je prema njima jako malo i čini mi se da nikako ne možemo u borbi da im se odupremo. Učinimo, dakle, ovako; neka dvojica od vas, Gojislav i Radoslav ostanu, a vi ostala trojica uzmite svaki po deset spretnih ljudi sa trubama i rogovima i popnite se na brda pa se po vrhovima brda tako razmjestite da Grci izgledaju u sredini. Ja ću sa ovima koji su sa mnom usred noći provaliti u njihov logor. Kad budete čuli glas trube i roga, isto tako i vi na brdima uokolo oglasite se jekom truba i rogova i glasnom vikom. Potom spuštajući se malo po malo, približite se njihovom logoru, i kad budete blizu, nemojte se plašiti, već budite hrabri i muški se borite. Svemogući Bog naime, predaće ih u naše ruke.“
Vojislav je poslao i jednog Baranina da „upozori“ Kursilija na oprez, jer na njega ide i opkoljava ga velika vojska. O tim ratnim i strateškim potezima Momir M. Marković, u knjizi Crnogorski rat, zaključuje: „Ovo je prva velika crnogorska bitka o čijem su ishodu, prema izvorima, odlučivali brzi manevar, iznenadni udar i ratne varke.“
Okršaj na Rumiji
Do okršaja je došlo na Rumiji, kod Tuđemila, u noći 6. na 7. oktobar 1042. godine. Vojislav je tiho nastupajući likvidirao grčke straže, što je dodatno uznemirilo Kusilijevu vojsku. U tom trenutku, na znak trube, dukljanski vojnici su počeli da duvaju u rogove i da strašno viču. To je bio znak Vojislavljevim sinovima da urade kako su se dogovorili: „A sinovi kraljevi koji bijahu po brdima isto tako počeše odavde i odande trubiti u trube i rogove i vikati. Zatim, lagano se spuštajući niz strane brda, približavahu se neprijateljima, a isto tako je učinio i kralj. Grci se zaista počeše jako plašiti, pa pošto su slušali kako se oni sporo spuštaju, a kako je bila noć i nijesu mogli da vide, mislili su da se radi o veoma velikoj vojsci, kao što su bili čuli od Baranina. A kad su čuli da je zvuk truba, rogova i vike već blizu i da na njih navaljuju, spopade ih strah, i okrenuše se u bijeg. Kad je pak kralj saznao, a i oni koji su sa njim bili, da Grci bježe, navališe kad se zora približavala na njihov logor, da ih ranjavaju, sijeku i ubijaju goneći ih pred sobom. Isto tako i kraljevi sinovi su ih na sve strane udarali i sjekli...“
Zetska vojska do nogu je potukla Grke, to jest Vizantince. Po vizantijskim izvorima bilo je 40-60.000 mrtvih i sedam palih stratega-zapovjednika, tj. generala. U isto vrijeme je Gojislav, sin kneza Vojislava, u blizini Klobuka, vodeći dukljanske odrede, „pobijedio kombinovanu raško-bosansko-humsku vojsku, koja se kod Bara trebala spojiti s vizantijskom“.
Okretanje zapadnoj civilizaciji
Poslije ove pobjede Duklja, tj. Zeta, bila je prva od južnoslovenskih kneževina kojoj je priznata nezavisnost od Vizantije. To je imalo značaja ne samo za prvu crnogorsku državu, nego i za istoriju ostalih južnoslovenskih, pa i evropskih država. Došlo je do buđenja težnji za oslobođenjem od Vizantije i okretanje zapadnoj civilizaciji. Vojislav je nakon ove bitke proširio svoju vlast na Travuniju i Zahumlje. Na taj način Duklja je faktički postala novi centar Južnih Slovena. Uz samostalnu državu Vojislav je nastojao da obezbijedi i samostalnu crkvu. Crkva je u to vrijeme bila jedinstvena. U Duklji je bilo ćedište biskupije, nad kojom su prevlast imale metropolije ili glavne crkve, koje su bile u Skadru, Draču, Splitu ili Dubrovniku.
Pravo priznanje državne samostalnosti, ostvario je Vojislavljev sin Mihailo, dobijanjem titule „rex Sclavorum“ (kralj Slovena) od pape Grgura VII 1077/78. godine. Samostalnost crkve ostvario je Mihailov sin Bodin (unuk kneza Vojislava), kada je Barska (Dukljanska) biskupija uzdignuta na rang nadbiskupije. Papa Kliment je u Vatikanu, 8. januara 1089. godine, uputio poslanicu kojom priznaje palijum (palijum, lat. pallium – arhijerejski ogrtač ili odora, koju nose samo pape i nadbiskupi) dukljanskom i barskom arhiepiskopu Petru i slavi „Bodina, najslavnijeg kralja Slovena“.
