Bolesław organized his first expedition east, to support his son-in-law Sviatopolk I of Kiev, in 1013, but the decisive engagements were to take place in 1018 after the peace of Budziszyn was already signed. At the request of Sviatopolk I, in what became known as the Kiev Expedition of 1018, the Polish duke sent an expedition to Kievan Rus' with an army of 2,000–5,000 Polish warriors, in addition to Thietmar's reported 1,000 Pechenegs, 300 German knights, and 500 Hungarian mercenaries. After collecting his forces during June, Bolesław led his troops to the border in July and on 23 July at the banks of the Bug River, near Wołyń, he defeated the forces of Yaroslav the Wise, Prince of Kiev, in what became known as the Battle of the River Bug. 

Yaroslav retreated north to Novgorod, opening the road to Kiev. The city, which suffered from fires caused by the Pecheneg siege, surrendered upon seeing the main Polish force on 14 August. The entering army, led by Bolesław, was ceremonially welcomed by the local archbishop and the family of Vladimir I of Kiev. According to popular legend Bolesław notched his sword (Szczerbiec) hitting the Golden Gate of Kiev. Although Sviatopolk lost the throne soon afterwards and lost his life the following year, during this campaign Poland re-annexed the Red Strongholds, later called Red Ruthenia, lost by Bolesław's father in 981.