Партия умеренных стремилась сохранить город для императора и заперлась в Карфагене. Тогда Стотза начал его осаду. Он уже был близок к захвату города, когда в Северную Африку из Сицилии прибыл Велисарий. Видимо, использовав разногласия в лагере восставших и опираясь на помощь Феодора Каппадокийца, он сумел отколоть от Стотзы значительное число воинов. Вскоре по прибытии Велисария в его распоряжении было уже две тысячи воинов. После этого Стотза отступил, но не сложил оружия.
Решительное сражение между войсками Велисария и повстанческой армией Стотзы произошло в 536 г. около города Мембресы, на берегу реки Баграда. Победа досталась Велисарию, более опытному в сражениях полководцу. Велисарий не решился преследовать Стотзу и возвратился в Карфаген. Здесь его ожидало тревожное известие о солдатском восстании в собственной армии в Сицилии, заставившее его поспешно покинуть Африку.
Но восстание воинов Стотзы продолжалось. Восставшие одержали блестящие победы в Нумидии. На сторону Стотзы перешла целая армия правителя Нумидии Маркелла. Победы Стотзы так обеспокоили Юстиниана, что он послал в Северную Африку своего племянника патрикия Германа, наделив его большими полномочиями. Герман тотчас произвел перепись всех солдат, сохранивших верность империи. Оказалось, что только одна треть войска осталась в Карфагене и других городах на стороне императора, а все остальные ушли к Стотзе. Экстренными мерами Герману удалось вернуть часть солдат в свою армию: им было выплачено все жалование, даже за то время, когда они сражались против правительства, всем возвращавшимся под знамена императора даровалась полная амнистия и раздавались щедрые подарки. Тем не менее, Стотза продолжал борьбу. Он сумел привлечь на свою сторону некоторые племена маврусиев. Стотза даже пытался наступать на Карфаген, но потерпел неудачу.
В 537 г. близ местечка Скале Ветерес в Нумидии повстанческая армия встретилась с войсками Германа. Превосходство сил было на стороне Германа, и он выиграл сражение. Немалую роль в этом сыграла позиция некоторых вождей маврусиев, внезапно перешедших на сторону Германа. Стотза принужден был скрыться в Мавретанию. Однако брожение в византийских войсках в Африке не утихало. Зимой 537/38 г. вспыхнуло восстание карфагенского гарнизона под руководством Максимина, с трудом подавленное Германом. Вскоре Герман был отозван Юстинианом из Африки, и ее окончательное замирение было вновь Поручено евнуху Соломону.
Для восстановления порядка Соломон стал проводить суровую чистку армии. Он выселил из провинции всех вандалов, построил по всей стране многочисленные укрепления, требовал строгого соблюдения римских законов. К 539 г. Соломону удалось разбить непокорные племена маврусиев в горах Авреса, захватить области Заба в Первой Мавретании и временно установить в Африке мир. Но этот мир длился только четыре года. В 543 г. военные действия против маврусиев возобновились. В 544 г. в битве у местечка Циллий, около Тебесты, византийские войска были наголову разбиты маврусиями Триполи и Бизацены, а сам Соломон, наместник Африки, убит.
Весной следующего, 545 г. началось второе восстание Стотзы. Прибыв из Мавретании, он вновь поднял восстание в Бизацене против преемника Соломона — Сергия. Стотзу поддержали маврусии и местное население. Повстанцы разбили армию наместника Бизацены Имерия и захватили в плен его самого. Воины Имерия присоединились к войскам Стотзы, которые овладели затем крупным приморским городом Гадруметом. Повстанцы стали фактическими хозяевами всей Бизацены. Стотза снова достиг большой власти, и множество византийских воинов опять спешили под его знамена.
В этот критический момент Юстиниан совершил ошибку, послав в Северную Африку сенатора Ареовинда. Не сведущий в военных делах, он мало походил на полководца, способного спасти Африку. Император усугубил свой промах, разделив власть в провинции между Сергием и Ареовиндом: первому поручалось вести борьбу с повстанцами в Нумидии, второму — в Бизацене. Между двумя правителями вскоре вспыхнула смертельная вражда, породившая бесконечные распри, которые были на руку восставшим. Сергий не хотел помогать Ареовинду и согласовывать действия обеих армий.
В 545 г. войска Стотзы наголову разбили отряд византийцев у местечка Тацеа, расположенного вблизи города Сикка Венерия, в области Зевгитана. Однако повстанцы потеряли в этом сражении своего храброго вождя, что было для них тяжким ударом. Место Стотзы во главе повстанцев занял некий Иоанн, сумевший снова сплотить всех недовольных византийским владычеством.
Убедившись, что распри между правителями провинции только способствовали усилению повстанцев, Юстиниан отозвал, наконец, Сергия и передал всю власть в Африке Ареовинду. Однако его единоличное правление не принесло желанного правительству умиротворения провинции. Уже через два месяца после отъезда Сергия она вновь была охвачена гражданской войной.