Having reached its pinnacle during the long reign of emperor Basil II, the Byzantine empire enters, following his death in 1025, a steady decline that is shortly to become evident - and specifically so in the Balkans. There, the elimination of the perennial Bulgarian threat, combined with insensitive taxation policy reversals, helped spur liberation movements. Around 1035, Stefan Vojislav asserted full independence for Duklja. At first, defeated and taken prisoner to Constantinople, with his realm annexed, he managed to escape, return and rekindle the struggle.

Taking advantage of guerilla warfare and the distracting effects of other uprisings, he staved off several punitive expeditions, asserting partial control over the principalities of Travunija and Zahumlje in the process. Thus, by 1040 his state stretched in the coastal region from Ston in the north, down to the Lake of Skadar, where he set up his capital, with other courts in Trebinje, Kotor, and Bar.

In 1042, the new emperor Constantine IX decides to field a more serious army against Duklja, aided by a coalition of three bribed neighboring Serbian principalities. The ensuing battles ended in total victory for Vojislav, accompanied by further expansion. Thus, Duklja becomes the leading Serbian state organization that replaced - in terms of leadership - the onetime "baptized" or "evangelized" Serbia, centered in Raska; it is to occupy this position until the turn of the 11th century. Vojislav spent the rest of his rule in peace, until his death in ca. 1051. He was succeeded by his widow and five sons - Gojislav, Predimir, Mihailo, Saganek, and Radoslav.