Во времена правления Византии Дукля представляла собой периферийную архонтию во главе с собственным князем, который формально признавал верховенство императора, однако обладал значительной автономией.
В начале XI века таким князем в Дукле был Стефан Воислав (ок. 1040 – ок. 1052) – родоначальник дуклянской княжеской династии Воиславлевичей. При них Дуклянское княжество обрело весомую политическую силу. В разные периоды в его состав входили Требинье, Захумье, Рашка, Босния и прибрежные города Адриатики. Правление Воиславлевичей проходило в условиях острой борьбы с Византийской империей и активного маневрирования между Востоком и Западом.
Стефан Воислав был родственником князя Владимира, а его жена, вероятно, являлась племянницей болгарского царя Самуила. Иными словами, династия Воиславлевичей тоже была связана с Первым Болгарским царством.
Стефан Воислав, несмотря на то, что находился под сюзеренитетом Византии, не был ей верным союзником. Он не раз пытался освободиться от власти Империи. Первый раз оказался неудачным, и Стефан Воислав был пленен. Побывав в плену в Константинополе, он вскоре бежал оттуда, а вернувшись на родину, разбил посланную императором карательную экспедицию, сделавшись «независимым» правителем Дукли. В 1042 году Византия попыталась вернуть непокорное княжество. Император Константин IX Мономах заручился поддержкой правителей Рашки, Боснии и Хума, и их войска с двух сторон двинулись на Дуклю. Решающее сражение произошло в начале октября 1042 года в горной местности между Баром и Црмницей, в котором победу одрежал Стефан Воислав. Эта победа в битве под Баром окончательно обеспечила политическую независимость Дукли от Византийской империи.
Сербы расправляются с византийцами в Битве под Баром. Фрагмент из Мадридской Скилицы
После смерти Стефана Воислава около 1043 года власть перешла к его младшему сыну Михаилу (ок. 1052–1081). Он внес значительные изменения во внешнюю политику княжества, прежде всего, улучшив отношения с Византией. Он заключил мир с императором Константином и даже породнился с ним, взяв в жены его племянницу. Быть может, именно тогда Византия передала дуклянскому князю город-порт Котор, а кроме того, василевс даровал Михаилу титул протоспафария – один из самых высоких титулов при императорском дворе.
Отношения между ними изменились после кризиса, переживаемого Византией в 1070-е годы. Поражение от турок-сельджуков при Манцикерте в 1071 году и утрата позиций в Южной Италии ослабили империю, чем попытался воспользоваться Михаил Воиславлевич. В 1072 году он поддержал антивизантийское восстание болгар, направив к повстанцам своего сына Константина Бодина и военачальника Петрила. Сначала восставшие под предводительством Бодина действовали успешно и сумели захватить Ниш и Охрид, а Константин, будучи потомком царя Самуила, даже был провозглашен болгарским царем. Но затем византийцам удалось разбить повстанцев в битве при Пауне, а самого Бодина захватить в плен. Он оставался в Константинополе в плену до 1078 года, пока не был освобожден людьми, нанятыми его отцом. Способствовало этому во многом то, что в это время Византию сотрясали большие волнения, а император Михаил был свергнут.
С этого времени Дукля все больше сближается с Западом, в т. ч. с норманнами, которые, заняв южную Италию, стремились теперь к экспансии на Балканы. Так, вернувшись из плена, Константин Бодин берет в жены норманнскую принцессу. В то же время Михаил укрепляет связи с папой римским. Он поддерживал переписку с папой Григорием VII и просил его признать королевский титул, а также прислать ему королевские регалии, как это было сделано немногим ранее в отношении хорватского короля Звонимира. Но, по всей видимости, этого не произошло, хотя в 1078 году Папа и обратился в письме к Михаилу как к «славянскому королю» (Slavorum Regi), что, впрочем, скорее было просто знаком особого расположения, а не реальным признанием титула. Тем не менее, Воиславлевичи очевидно использовали титул короля, однако неизвестно, с какого точно момента это началось. «Летопись попа Дуклянина» всех правителей Дукли называет «королями», а потому не может быть достоверным источником.
С 1081 года, после смерти Михаила Воиславлевича, его сын Константин Бодин (1081–ок. 1101) начинает править самостоятельно. Современники изображают Константина Бодина как ненадежного союзника Византии. Во время битвы Византии с норманнами при Диррахии в 1081 году Бодин фактически уклонился от участия в сражении на стороне императора, что способствовало победе норманнов. Воспользовавшись ослаблением византийского контроля, он занял Рашку, Боснию и ненадолго овладел самим Диррахием.
Таким образом, при Бодине Дуклянская держава достигает своего наибольшего расцвета и территориального размаха: она включает Хум, Травунию, часть Боснии и Рашки. Ее границы проходят вдоль побережья от реки Неретвы и города Травника на севере до реки Дрим на юге, а на востоке до гор Явор, Ястребац и города Звечана (совр. Косово) на востоке. В 1089 году Константин Бодин добился от антипапы Климента III поднятия статуса епископии Бара до архиепископии.
Несмотря на внешние успехи, внутренняя устойчивость Дуклянской державы не была стабильной. После смерти Бодина около 1101 года начался затяжной династический кризис. Власть переходила от одного представителя рода Воиславлевичей к другому, сопровождаясь мятежами, вмешательством соседей, междоусобицами. Постепенно усиливалось влияние соседнего княжества Рашки, чьи жупаны все активнее вмешивались в дуклянские дела.
Рашка во второй четверти XII в. смогла укрепиться за счет соперничества Византии и Венгерского королевства на этих территориях. С 1168 года в Рашке правит великий жупан Стефан Неманя (1168–1196). Интересно, что по стечению обстоятельств родился он именно в Дукле, когда сюда бежал его отец Завида. Долгое время Стефан Неманя был вынужден признавать зависимость от византийского императора Мануила I Комнина, но при этом готовился к решительным шагам, ожидая благоприятного момента, чтобы выйти из-под власти империи. Такой момент наступил после смерти Мануила, ставшей началом стремительного ослабления византийского влияния на Балканах. Отказавшись от подчинения новым византийским властям, Стефан Неманя перешел к активным военным действиям. В союзе с венгерским королем Белой III он нанес ряд ударов по византийским владениям, а затем продолжил экспансию и на соседние земли.
Неизвестный художник. Портрет Константина Бодина, царя Болгарии и короля Дукли
В это время в Дукле правил князь Радослав, который не мог оказать серьезного сопротивления Немане. От прежних владений Воиславичей в его власти осталась лишь узкая полоса побережья Адриатики, а сам Радослав уже носил титул князя, а не короля, как все предыдущие Воиславлевичи. Это свидетельствует о том, что от былой мощи Дуклянской державы к тому моменту не осталось и следа. Окончательный удар ей был нанесен около 1185 года, когда Стефан Неманя завоевал оставшиеся земли князя Радослава. Это событие ознаменовало конец независимости Дуклянской державы и завершение истории первой черногорской династии Воиславлевичей.