Po stabilizaciji slovenskih plemena duž obale Jadranskog mora i prihvatanja hrišćanstva došlo je do formiranja prvih srednjevijekovnih država. Vojislavljevići su prva crnogorska dinastija koja je vladala Dukljom od kraja X do kraja XII vijeka. Dobila je ime po knezu Vojislavu, iako je prvi vladar iz ove porodice, o kome se nešto više zna, bio knez Vladimir, po predpostavci sin arhonta Petra, Vojislavov stric ili brat od strica. Vojislav se definitivno oslobodio vizantijske dominacije i proširio teritoriju Duklje na Travuniju i oblast Drača. Vojislavov sin Mihailo, prvi je dukljanski vladar za koga se pouzdano zna da je imao titulu kralja potvrđenu od strane Pape Grgura VII. Nasljednik kralja Mihaila, kralj Bodin proširio je državu. Osvojio je Rašku i Bosnu i izdejstvovao od Rima podizanje barske biskupije u rang nadbiskupije. Bodin je uspostavio veze sa Normanima iz južne Italije i oženio se Jakvintom, ćerkom normanskog vladara iz Barija. Dolazio je u direktan kontakt sa predvodnicima krstaškog pohoda 1099. godine. Krajem XII vijeka Duklja je dostigla teritorijalni vrhunac. Obuhvatala je teritoriju od rijeke Vojuše do Neretve i od Jadranskog mora do sjevernih granica Raške i Bosne. Nakon smrti kralja Bodina, moć Duklje počinje da slabi. Nastupa period raspri (1108 – 1185), čestih unutrašnjih sukoba i razdora koji su je na kraju uništili. Poslednji kraljevi iz dinastije Vojislavljevića bili su efemerni. Vladimir, Dobroslav, Đorđe, Grubiša, Gradhina, knez Radoslav nijesu uspjeli da sačuvaju državu od vizantijskog i raškog uticaja. Na kraju je u Duklji preovladao vizantijski uticaj, a oko 1185. godine raški župan Stefan Nemanja ju je osvojio.
Arhont Petar
Olovni pečat arhonta Petra predstavlja najstariji materijalni trag dukljanske državne tradicije. Na pečatu arhonta Petra, koga Pop Dukljanin naziva Petrislavom, stoji na grčkom jeziku utisnut natpis: PETAR ARHONT DUKLJE AMNEN. Uprskos činjenici da je Arhont Petar bio vizantijski vazal, od sredine X vijeka dukljanska kneževina je bila formirana i jasno razgraničena od susjednih slovenskih kneževina i ostalog vizantijskog područja. Pop Dukljanin u svom djelu navodi da je otac Svetog Kneza Vladimira bio arhont Petar, a ktitorstvo crkve Svete Marije u Krajini se takodje pripisuje njemu .
Jovan Vladimir
Vladao je Dukljom krajem X vijeka od oko 990 do 1016. godine. Teritorija njegove države prostirala se između rijeke Bojane i Boke Kotorske, i između Jadranskog mora i gornjeg toka rijeke Morače. Neuspiješno je Vladimir pokušao da sklopi savez sa Vizantijom, kako bi suzbio namjere makedonskog cara Samuila da pokori Duklju. Car Samuilo ju je 997. godine napao. Do prvog sukoba makedonske i dukljanske vojske došlo je oko rijeke Bojane. U toj bici makedonska vojska je pobijedila, a knez Vladimir je zarobljen i odveden na Samuilov dvor u Prespu. U zatočeništvu kod makedonskog cara, knez Vladimir je ostao izvjesno vrijeme. Oženivši se carevom ćerkom Kosarom, vratio se u Duklju kao Samuilov zet namjesnik. Pored Duklje, Vladimir je dobio na upravu i dračku oblast. Od tada pa sve do smrti cara Samuila (1014), knez Vladimir je bio lojalan makedonskom caru.
Novi makednosni vladar, Vladislav, koji je 1015. godine nasilno preuzeo vlast od cara Radomira, namjeravao je da osvoji dukljansku državu i Drač. Vladislav je odlučio da ukloni Vladimira i pozvao ga je u svoj dvor u Prespu. Vladimir je, nakon carevog obećanja da mu se ništa loše neće dogoditi, prihvatio poziv i uputio se u Prespu. Car Vladislav je pogazio obećanje i ubio Vladimira 1016. godine. Vladimir je sahranjen u Prespi, a nakon tri godine njegova žena je mošti prenijela u Krajinu u crkvu sv. Marije Krajinske. Proglašen je za sveca i njegov kult je bio rasprostranjen u Duklji (Zeti), Albaniji i Makedoniji. Žitije sv. Vladimira potiče s početka XII vijeka. Grčka legenda o Vladimiru, prvi put je publikovana od strane dračkog arhiepiskopa Kozme 1690. godine. Mošti sv. Vladimira su 1215. godine prenšene u Drač gdje je postao svetac zaštitnik grada. Albanski feudalac Karlo Topija, radi razvijanja kulta sv. Vladimira podigao je 1381. godine crkvu u Elbasanu u kojoj su pohranjene mošti sv. Vladimira. Kult sv. Vladimira i danas je prisutan u Krajini. Na planini Rumiji, na Duhove ili Trojčin dan, odvija se procesija u kojoj lokalno stanovništvo po utvrđenom ritualu iznosi na najveći vrh Rumije najstariju crnogorsku relikviju – krst sv. Vladimira.
Vojislav
Iako izvorima se pominje i kao Dobroslav, po njemu je dinastija dobila ime Vojislavljevići. Na dukljanski presto je ustoličen oko 1018. godine i vladao je Dukljom kao vizantijski vazal. Uspio je da zbaci vizantijsku vlast i da osamostali Duklju oko 1035. godine, ali je taj uspjeh bio kratkotrajan pa je 1036. godine Duklja opet bila u sastavu Vizantije, a Vojislav odveden u Carigrad kao talac. Uspio je da pobjegne iz Carigrada i da se ponovo osamostali u Duklji, 1039. ili 1040. godine. Sukobio se s vizantijskom vojskom 1040. godine, na prostoru Crmnice, uspjevši da joj nanese poraz. U ustanku makedonskih Slovena protiv Vizantije, pod rukovodstvom Petra Deljana 1042. godine, podržavao je pobunjenike iz Dračke teme, što je Vizantiji dalo povod da preduzme novi pohod protiv Duklje. Presudan obračun između Duklje i Vizantije odigrao se 1042. godine. Vizantijska vojska se okuplila u Draču, a u pohodu protiv Duklje Vizantiji su se pridružili raški župan, bosanski ban i humski knez Ljudovit, koji je preuzeo komandu nad cijelom savezničkom vojskom. Napadi vizantijske vojske i njenih saveznika pod komandom Ljutovida otpočeli su istovremeno. Vizantijska vojska je napadala iz pravca Skadra, a Ljudovitova iz pravca Trebinja. Vojislav je prvo pobijedio vizantijsku vojsku kod Bara oktobra 1042. godine (Barska bitka), a potom je njegov sin Gojislav pobijedio združenu raško – bosansko – humsku vojsku u okolini Klobuka. Nakon ovih pobjeda Duklja je u potpunosti zbacilia vlast Vizantije, zauzela cjelokupnu dračku oblast do rijeke Vojuše i ostvarila dominaciju nad Travunijom. Vojislav je najvjerovatnije umro 1043. godine. Vladao je Dukljom oko dvadeset pet godina. Umro je u svom dvoru. Sahranjen je u dvorskoj kapeli sv. Andrije u župi Papratna. Imao je pet sinova: Gojislava, Radoslava, Mihaila, Saganeka i Predimira.
Kralj Mihailo
Poslije smrti svoga oca Vojislava vladao je u Duklji kao savladar sa braćom i majkom. Direktno su mu bile potčinjene župe Oblik, Prapratna i Crmnica. Između Mihaila i braće izbili su nesporazumi, ali on nije mogao da nametne svoju prevlast, već je sa njima sklopio sporazum prema kome je priznao vrhovno pravo vlasti u zemlji bratu Radoslavu kao i njegovim nasljednicima. Nakon smrti majke, Mihailo je uspio da zauzme presto u Duklji, oko 1046. godine. Promijenio je spoljno politički orijentaciju Duklje, uspostavivši dobre odnose s Vizantijom. Drugi put se oženio rođakom vizantijskog cara Konstantina IX Monomaha i dobio titulu protospatora. Raskinuo je ugovor sa bratom Radoslavom i njegovim sinovima i njihove teritorije u Duklji dao je na upravu svom najstarijem sinu iz prvog braka Vladimiru. Njegovi sinovi iz prvog braka Vladimir i Bodin osvojili su Rašku, ali je Mihailo upravu nad Raškom povjerio sinu iz drugog braka, Petrislavu. Mihailo se nakon dugog savezništva sa Vizantijom okrenuo protiv nje kada je 1072. godine izbio ustanak makedonskih Slovena pod vođstvom skopskog boljara Đorđa Vojteha. Ustanici su zatražili pomoć od Mihaila i on im je poslao oko trista vojnika sa svojim sinom Bodinom i vojskovođom Petrilom. Mihailo je prvi dukljanski vladar za koga se pouzdano može reći da je imao kraljevsku titulu. U jednom pismu iz januara 1078. godine papa Grgur VII mu se obraća kao kralju Slovena. Mihailo je najvjerovatnije umro oko 1082. godine, a sigurno prije 1085. godine.
Konstantin Bodin
Tokom vladavine njegovog oca kralja Mihaila bio je uključen u državničke poslove. Bodin je sa bratom Vladimirom osvojio Rašku, a 1072. godine, po naređenju svog oca, pomagao je sa dukljanskom vojskom makedonske ustanike protiv Vizantije. Ustanici su ga u Prizrenu krunisali za cara, sa imenom Petar, nakon čega je postao vođa ustanka. Predvodio je ustaničku vojsku u Podunavlju i osvojio je Vidin, ali je ubrzo doživio poraz od vizantijske vojske u Skoplju, i potom je bio zarobljen kod Taona na južnom Kosovu. U Vizantiji je kao zarobljenik proveo nekoliko godina. Prvo je zatvoren u Carigradu u manastiru sv. Srđa i Vlaha, a zatim je kao sužanj bio odveden u Antiohiju (Sirija). Uspio je da pobjegne 1078. godine i po povratku u Duklju dobio je na upravu župu Grbalj sa Budvom. Bodin se 1081. godine oženio Jakvintom, ćerkom normanskog vladara iz Barija, Arhiriza. Kada je umro kralj Mihailo 1082. godine Bodin je postao kralj, ali tek nakon sukoba sa svojim stricem Radoslavom, koga je pobijedio i protjerao u Travuniju. Sukobio se i sa knezom Branislavom, sinom kralja Radoslava, ali je uz posredovanje barskog biskupa Petra došlo do izmirenja. Pošto je sredio unutrašnje prilike u zemlji, Bodin je 1083. i 1084. godine preduzeo pohode na Rašku i Bosnu. Oba pohoda su bila uspješna. Bosna i Raška su ušle u sastav Duklje. Bodin je u osvojenu Rašku kao namjesnike postavio dva župana sa svog dvora, Vukana i Marka. U Bosni je Bodin za kneza postavio Stevana.
U borbi protiv Franaka osvojio je čitavu dračku oblast i Drač 1085. godine i potom je grad predao Vizantiji. Uspio je da barsku biskupiju podigne na rang nadbiskupije. Na Bodinov zahtjev barskom biskupu Petru u Rimu je 8. januara 1089. godine izdana papska bula, kojom je Petar postao barski nadbiskup. Dukljansko-barska nadbiskupija dobila je sufraganstvo nad episkopijama: dukljanskom (barskom), kotorskom, ulcinjskom, svačkom, skadarskom, drivaskom, polatskom, srpskom, bosanskom i travunskom. Krajem XI vijeka ponovo su izgbili untrašnji sukobi u Duklji između Bodina i sinova njegovog brata od strica Branislava (Predhine, Petrislava, Gradhine, Tvrdislava, Dragila, Draghine i Grubeše). Bodin je Branislava zarobio i bacio u tamnicu u Skadru, dok se ostala rodbina Branislavljeva sklonila u Dubrovnik, što je bio povod za rat između Bodina i Dubrovnika. Dukljanski namjesnik u Bosni, knez Stevan opsijedao je Dubrovnik sa vojskom 1104. godine. Bodin je uspio da zauzme Dubrovnik, da protjera svoje rođake, i potom je podigao tvrđavu, koju je ubrzo predao Dubrovčanima. Nakon 26 godina vladavine Bodin je umro 1108. godine i sahranjen je u manastiru sv. Srđa i Vlaha na Bojani. Za vrijeme Bodinove vladavine Duklja je dostigla svoj državni i teritorijalni zenit. Nakon Bodinove smrti, moć Duklje je naglo opadala zbog čestih sukoba između Bodinovih nasljednika.
Dinastičke raspre i opadanje Duklje
Mihajlo Vojislavljević najstariji sin kralja Bodina naslijedio je oca na prijestolu 1108. godine, ali je ubrzo bio svrgnut. Dobroslav, sin kralja Mihaila Vojsilavljevića i vizantisjke princeze, polubrat kralja Bodina Vojsilavljevića je voljom naroda izabran za kralja, nasuprot pretenzijama nepopularne kraljice Jakvinte, Bodinove udovice. Njegova vladavina nije dugo potrajala jer je raški župan Vukan sa pretendentom na dukljansku krunu Kočaparom, sinom kralja Radoslava Vojislavljevića, napao Duklju i u bici na Morači porazio kralja Dobroslava. Dobroslav je zarobljen i odveden u Rašku, dok je raška vojska sa Kočaparom i Vukanom zauzela Duklju. Kočapar nije uspio da se zadrži u Duklji, već je prebjegao u Zahumlje, gdje je i umro. Dobroslav je kasnije bio pušten iz tamnice i vratio se u Duklju. Vladimir, ga je zatvorio u sakdarsku tamnicu, a Bodinova udovica Jakvinta i njen sin Đorđe su spremili zavjeru protiv Dobroslava. Oni su ga izvukli iz tamnice i zatvorili u manastir sv. Srđa i Vlaha na Bojani gdje je Dobroslav umro kao monah. Nakon što je raški župan Vukan pokorio Duklju, u njoj je, kao svog vazala, postavio Vladimira za dukljanskog kralja. Vladimir je bio oženjen Vukanovom ćerkom. Bio je eksponent raške struje u Duklji. Stradao je kao žrtva dinastičkih sukoba. Otrovan je 1118. godine po naređenju kraljice Jakvinte i njenog sina Đorđa.
Đorđe, sin kralja Bodina Vojislavljevića, se svojom majkom kraljicom Jakvintom suprotstavio kralju Vladimiru i raškom uticaju u Duklji. Jakvinta i Đorđe su dvorskom spletkom uspjeli da otruju Vladimira, nakon čije smrti je Đorđe 1118. godine postao kralj, ali se njegova vladavina završila iste godine. Đorđe je namjeravao da likvidira i ostale rođake koji su pretendovali na njegov prijesto. Pokušao je da pohvata sinove kneza Branislava, ali bez uspjeha, jer su se oni sklonili u Drač, gdje se nalazio i njihov stric Gojislav. Vizantija je uz pomoć ovih dukljanskih emigranata napala Duklju. Đorđe je bio primoran da se pred vizantijskom vojskom, u kojoj su bili i njegovi rođaci, povuče u tvrđavu Oblik na Tarabošu, a vizantijska vojska je osvojila Skadar i ubrzo čitavu Duklju. Kraljica Jakvinta je uhvaćena u Kotoru i kao zarobljenica poslata u Carigrad gdje je umrla. Kralj Đorđe se sklonio u Rašku kod župana Vukana, čime se završila njegova prva vladavina u Duklji.
Nakon poraza kralja Đorđa, Vizantija je u Duklji za kralja postavila Grubešu. Đorđe je pomoću raške vojske napao Duklju, porazio Grubešu 1125. godine i preuzeo vlast u Duklji, ali ne na cjelokupnoj teritoriji, već je vlast morao da dijeli sa braćom kralja Grubeše, Draghinom i Dragilom. Sa njima je uspostavio prijateljske odnose, pa je čak, na predlog Dragila, kralj Đorđe napao Rašku i osvojio je. Pošto je učvrstio svoju vlast i proširio državnu teritoriju, Đorđe je uspostavio vlast u čitavoj Duklji i pokušao da uništi svoje rođake, koji su mu se suprotstavili. Zarobio je i bacio u tamnicu Mihajla, sina kralja Vladimira, i Dragila, dok je Draghina sa sinovcima uspio da pobjegne u Drač pod vizantijsku zaštitu, gdje im se iz Zahumlja pridružio Draghinin brat Gradhina.
Protiv Đorđa je osnovana druga koalicija između njegovih rođaka i Vizantije. Vizantijska vojska, zauzela je Duklju do Bara i Podgorice, ali je zaustavila napredovanje jer je glavnokomandujući vizantijske vojske morao da ode u Carigrad. Đorđe je iskoristio predah vizantijske vojske, i napao je Oblik u kome su se utvrdili njegovi rođaci. Pod Oblikom, Đorđe je pobijeđen, nakon čega je uslijedila vizantijska ofanziva kojoj su se pridružili i Rašani. Đorđe se povlačio pred vizantijskom vojskom i utvrdio se u tvrđavi Oblun na Malom Blatu, odakle je pružao otpor vizantijskoj vojsci. Među Đorđijevim vojnicima izbila je pobuna i Oblun je zauzet, a kralj Đorđe je zarobljen i poslat u Carigrad u tamnicu, gdje je i umro. Za dukljanskog kralja postavljen je Gradhina.
Nakon što je Vizantija porazila kralja Đorđa 1118. godine, Grubeša je postao vizantijski štićenik i vladar u Duklji. Vizantija mu je povjerila upravu u osvojenoj Duklji i komandu nad vojskom koja je ratovala protiv Đorđa. Vladao je u Duklji do 1125. godine kada ga je kod Bara porazio Đorđe, koji je uz pomoć Raške uspio da povrati vlast u Duklji. Grubeša je u bici kod Bara poginuo ili je ubzo umro. Sahranjen je u crkvi sv. Đorđa u Baru.
Nakon drugog dukljansko–vizantijskog rata u kome je kralj Đorđe poražen i zarobljen u tvrđavi Oblon, Vizantija je za dukljanskog kralja postavili Gradhinu. Bio je vizantijski eksponent, a moć i teritorijalni opseg Duklje su u periodu njegove vladavine bili već uveliko umanjeni. Poslije smrti Gradhina je sahranjen u crkvi sv. Srđa i Vlaha na Bojani.
Radoslav, poslednji vladar iz dinastije Vojislavljevića, presto je naslijedio od svoga oca kralja Gradhine, ali je za potvrdu svoje vlasti morao da ide u Carigrad, gdje mu je vizantijski car Manojlo Komnen (1143 – 1180) dao odobrenje da vlada u Duklji. Za razliku od svog oca i svih dukljanskih vladara, Radoslav nije nosio titulu kralja već kneza, što je bio znak degradacije moći i ugleda dukljanske države, njene potčinjenosti i vazalnog položaja prema Vizantiji. Radoslav je dijelio vlast sa svojom braćom Jovanom i Vladimirom i krajem njegove vladavine ili nakon njegove smrti, raški župan Stefan Nemanja je oko 1185. godine osvojio Duklju.