Upon hearing the news of his deposition, Skleros came to an agreement with local Armenian, Georgian and even Muslim rulers who all vowed to support his claims to the imperial crown. He successfully stirred up rebellion among his relatives and adherents in the Asian provinces, rapidly making himself master of Caesaria, Antioch, and most of Asia Minor.

After several navy commanders defected to Skleros's side, he dashed to Constantinople, threatening to blockade the Dardanelles. The rebel navy under Michael Kourtikios raided the Aegean and attempted to blockade the Dardanelles, but were defeated by the Imperial Fleet under the command of Theodoros Karantenos.

Having lost supremacy at sea, Skleros at once laid siege to the town of Nicaea, which was considered a key to the capital. The town was fortified by a certain Manuel Erotikos Komnenos, father of the future emperor Isaac Komnenos and progenitor of the Komnenoi dynasty.