Однако Алексей не мог находиться всюду одновременно, а опытных военачальников было мало; поэтому год или два спустя, когда империя столкнулась с двумя новыми, гораздо более серьезными мятежами, Русселя внезапно отпустили из плена, и он обнаружил, что вместе с Алексеем воюет против двух новых претендентов на трон. Первым был Никифор Вриенний, который преданно сражался при Манцикерте, не желал дальше мириться с некомпетентностью Михаила Парапинака и его правительства и поднял мятеж в 1077 году; он пошел на Адрианополь, где его провозгласили василевсом. Неделю спустя он и его войско уже стояли у стен столицы. Мятеж Вриенния вполне мог стать успешным, если бы не второе восстание, почти одновременно начавшееся на Востоке. Его вождем стал стратиг фемы Анатолик Никифор Вотаниат. Как и Вриенний, он восстал против императора из высоких побуждений.

Вриенний первым появился на поле сражения, однако Вотаниат имел более благородное происхождение, поскольку родился в семье, относившейся к старой военной аристократии. Кроме того, он был сильнее, так как сумел подкупить сельджуков, нанятых Михаилом, чтобы ему противостоять. Ни тот ни другой не совершали прямого нападения на Константинополь, прекрасно зная от тайных осведомителей в столице, что недовольство народа растущими ценами скоро обострит ситуацию; так и случилось в марте 1078 года. Во всех уголках города начались беспорядки; многие правительственные здания сожгли дотла. Михаил, которому посчастливилось уйти живым, отрекся от престола и удалился в Студийский монастырь, а 24 марта Никифор Вотаниат триумфально вошел в Константинополь. Его соперника Вриенния схватили и ослепили.

Это было зловещее начало царствования. Вотаниат был толковым военачальником, но ничего не смыслил в политике; кроме того, ему было уже хорошо за семьдесят, и в попытке добиться трона он растратил большую часть своих сил. Не сумев справиться с кризисом, он мог лишь присутствовать при дальнейшем распаде империи. Старая партия государственной бюрократии развалилась, а с ней и власть сената; византийцам оставалось только молиться, чтобы хоть один из борющихся за власть военачальников оказался способен положить конец хаосу.

Три года спустя эта молитва была услышана. Вотаниат, в свою очередь, отрекся от престола в пользу молодого полководца-аристократа, который взошел на трон на Пасху 1081 года и правил следующие тридцать семь лет, подарив империи порядок, в котором она так отчаянно нуждалась, и управляя ею твердой и уверенной рукой. Этим человеком был Алексей Комнин, племянник Исаака I. Даже ему не удалось исправить последствия битвы при Манцикерте, но он сумел восстановить доброе имя Византии среди других государств.