In 998, Samuel launched a major campaign against the Duklja to prevent an alliance between Prince Jovan Vladimir and the Byzantines. When the Bulgarian troops reached Duklja, the Serbian prince and his people withdrew to the mountains. Samuel left part of the army at the foot of the mountains and led the remaining soldiers to besiege the coastal fortress of Ulcinj. In an effort to prevent bloodshed, he asked Jovan Vladimir to surrender. After the prince refused, some Serb nobles offered their services to the Bulgarians and, when it became clear that further resistance was fruitless, the Serbs surrendered. Jovan Vladimir was exiled to Samuel's palaces in Prespa.

The Bulgarian troops proceeded to pass through Dalmatia, taking control of Kotor and journeying to Dubrovnik. Although they failed to take Dubrovnik, they devastated the surrounding villages. The Bulgarian army then attacked Croatia in support of the rebel princes Krešimir III and Gojslav and advanced northwest as far as Split, Trogir and Zadar, then northeast through Bosnia and Raška and returned to Bulgaria. This Croato-Bulgarian War allowed Samuel to install vassal monarchs in Croatia.

Samuel's relative Kosara fell in love with the captive Jovan Vladimir. The couple married after gaining Samuel's approval, and Jovan returned to his lands as a Bulgarian official along with his uncle Dragomir, whom Samuel trusted. Meanwhile, Princess Miroslava fell in love with the Byzantine noble captive Ashot, son of Gregorios Taronites, the dead governor of Thessaloniki, and threatened to commit suicide if she was not allowed to marry him. Samuel conceded and appointed Ashot governor of Dyrrhachium. Samuel also sealed an alliance with the Magyars when his eldest son and heir, Gavril Radomir, married the daughter of the Hungarian Grand Prince Géza.