Część uczonych wychodząc od faktu, że Jan Włodzimierz nigdy nie należał do stronnictwa antybizantyńskiego i nie pomagał Bułgarii w wojnie przeciw Bizancjum, przyjmuje że Dukla i Zahumle zachowały status wasalny pod panowaniem bizantyńskim.
Niezależnie od tego jak sytuacja wyglądała, gdy źródła ponownie około połowy lat 30. mówią o Primorju, Zahumlem i Trawunią władał Stefan Wojsław. W 1035 rokuJ. Fine mówi o latach 1034-1036 odmówił on złożenia hołdu Bizancjum. Został jednak pokonany w otwartym boju przez bizantyńskiego stratega Dracza i odstawiony jako jeniec do Konstantynopola. W następnym roku zbiegłWedług Fine'a dopiero w latach 1038/1039. Po powrocie schronił się w góry wraz ze stale rosnącą liczbą zwolenników i w krótkim czasie oswobodził znaczną część swego księstwa. Kolejne ekspedycje bizantyńskie kończyły się niepowodzeniem. W jednej z nich zginął bizantyński dowódca. Wojsław nie występował do otwartej walki. Gdy wkraczali Bizantyńczycy, wycofywał się w góry, skąd nękał liczniejszą i lepiej uzbrojoną armię wroga nagłymi wypadami i zasadzkami. W 1040 roku na wybrzeżu dalmatyńskim rozbił się bizantyński okręt z ładunkiem złota. Wojsław zagarnął ładunek i odmówił wydania go Bizantyńczykom.