Постигавши врхунац током дуге владавине цара Василија II, византијско царство улази након његове смрти 1025. године у стални пад који ће ускоро постати очигледан - а нарочито на Балкану. Елиминација вишегодишње бугарске претње, у комбинацији са неосјетљивим преокретом пореске политике, помогла је потицајима покрета за ослобађање. Око 1035., Стефан Војислав је постигао потпуну независност за Дукљу. Испрва поражен и заробљен у Цариграду, анексираним краљевством, успео је да побегне, врати се и поново покрене борбу.

Искористивши герилска ратовања и ометајући ефекте других устанка, одустао је од неколико казнених експедиција, успостављајући делимичну контролу над кнежевинама Травуније и Захумље у том процесу. Тако се до 1040. године његова држава протезала у приморском крају од Стона на северу, до Скадарског језера, где је поставио свој главни град, са осталим судовима у Требињу, Котору и Бару.

1042., нови цар Константин IX. одлучује да на Дукљи постави озбиљнију војску уз помоћ коалиције три подмићене суседне српске кнежевине. Следеће битке завршиле су се победом за Војислава, праћенае даљим ширењем. Тако, Дукља постаје водећа српска државна организација која је заменила - у смислу вођства - некадашњу "крштену" или "евангелизовану" Србију, са центром у Рашкој; треба задржати овај положај до прелазног рока у 11. век. Остатак своје владавине Војислав је провео у миру, све до смрти око 1051. Наследила га је његова удовица и пет синова - Гојислав, Предимир, Михаило, Саганек и Радослав.