In 1087, Alexios faced a new invasion. This time the invaders consisted of a horde of 80,000 Pechenegs from north of the Danube, and they were heading for Constantinople. Alexios crossed into Moesia to retaliate but failed to take Dorostolon. During his retreat, the emperor was surrounded and worn down by the Pechenegs, who forced him to sign a truce and to pay protection money. In 1090 the Pechenegs invaded Thrace again, while Tzachas, the brother-in-law of the Sultan of Rum, launched a fleet and attempted to arrange a joint siege of Constantinople with the Pechenegs. Without enough troops to repel this new threat, Alexios used diplomacy to achieve a victory against the odds. Alexios overcame this crisis by bribing a horde of 40,000 Cumans, with whose help he surprised and annihilated the Pechenegs at the Battle of Levounion in Thrace on 29 April 1091.

This put an end to the Pecheneg threat, but in 1094 the Cumans began to raid the imperial territories in the Balkans. Led by a pretender claiming to be Constantine Diogenes, a long-dead son of the Emperor Romanos IV, the Cumans crossed the mountains and raided into eastern Thrace until their leader was eliminated at Adrianople. With the Balkans more or less pacified, Alexios could now turn his attention to Asia Minor, which had been almost completely overrun by the Seljuk Turks.