Bagrat's son George I launched a campaign to restore the Kuropalates's succession to Georgia and occupied Tao in 1015–1016. He entered in an alliance with the Fatimid caliph of Egypt, al-Hakim, forcing Basil to refrain from an acute response to George's offensive. As soon as Bulgaria was conquered in 1018 and al-Hakim was dead, Basil led his army against Georgia. Preparations for a larger-scale campaign against the Kingdom of Georgia were set, beginning with the re-fortification of Theodosiopolis.

In late 1021, Basil, at the head of a large Byzantine army reinforced by the Varangian Guard, attacked the Georgians and their Armenian allies, recovering Phasiane and continuing beyond the frontiers of Tao into inner Georgia. King George burned the city of Oltisi to prevent it falling to the enemy and retreated to Kola. A bloody battle was fought near the village Shirimni at Lake Palakazio on 11 September; the emperor won a costly victory, forcing George I to retreat northwards into his kingdom. Basil plundered the country and withdrew for winter to Trebizond.