В Карфагене восставшие разграбили город, захватили дома и земли, какие им приглянулись, а затем вышли из города, чтобы соединиться с другими отрядами восставших, теми, на кого Соломон возложил бесконечную осаду горы Аурес. Когда они собрались вместе, их общая численность составляла семь тысяч. Кроме того, с ним была тысяча вандалов. Четыреста человек из них составляли удравшие пленные. Они раньше направлялись к персидской границе из Константинополя, но недалеко от острова Лесбос обезоружили охрану на судах и поплыли не к Антиохии, а назад к Северной Африке, где они высадились на пустынном берегу рядом с горой Паппуа и отправились к горе Аурес. Они собирались объединиться с восставшими маврами, но вместо этого присоединились к восставшим солдатам Карфагена, которые их радостно приветствовали. Остальные вандалы были беженцами, скрывавшимися со времен падения Карфагена. Наконец они нашли единомышленников! Коней они добыли на почтовых станциях.
Восставшие выбрали командиром энергичного и умного фракийца по имени Стоцас и отправились в Карфаген, объявив всю провинцию Республикой Солдат. Они не ждали, что граждане станут им сопротивляться, прибыли к стенам Карфагена в сумерках седьмого апреля и раскинули там лагерь, собираясь продолжить путь на следующее утро. Но в тот вечер прибыл Велизарий по морю с сотней кирасиров и немедленно начал искать в разграбленном Карфагене оставшихся верными Юстиниану солдат. До утра ему удалось собрать две тысячи человек. Шестьсот были римские рекруты-кавалеристы, служившие в полиции и пятьсот - вандалы, пожилые люди, которым Велизарий позволил жить в их домах, и теперь они в знак благодарности решили ему помочь. В его войсках также были преданные ему мавры. Солдат, которые не принимали участие в восстании, осталось всего пятьсот человек. Но недаром говорили, что имя Велизария стоило пятидесяти тысяч солдат. Когда восставшие узнали о его внезапном возвращении, они решили, что против их восьми тысяч выставлено пятьдесят две тысячи солдат Велизария, покинули лагерь и быстро отправились в глубь Африки. Они направились к горе Аурес, где собирались заключить соглашение с маврами. Велизарий отправился за ними в погоню и догнал в пятидесяти милях от неукрепленного города в Мембресе, рядом с рекой Баград. Такой битвы он еще не знал - против него должны были сражаться его собственные солдаты.
Сейчас всю славу за сражение отдают святому Киприану, который, как свидетельствует легенда, появился на Пасху в храме Святого Киприана, переодетый в церковного старосту, но над головой у него сиял нимб. Тогда он разоружил убийц и заставил их пасть ниц. При Мембресе святой Киприан внезапно поднял ветер и начал сильно дуть в лица восставших, когда обе армии собирались начать сражение. Стоцас понимал, что из-за ветра стрелы его солдат потеряют скорость, и приказал половине кавалерии отправиться в спокойное место на правом фланге и начать стрелять оттуда. Этот маневр происходил медленно, кругом царила страшная неразбериха. Велизарий был во главе кавалерии и немедленно воспользовался беспорядком. В центре беспорядка находился эскадрон вандалов.
Вандалы не были лучниками и не понимали, что им делать - оставаться на месте или передвигаться. Они поддались под напором Велизария, и армия восставших была разделена на две части. Они отступили, когда колонна Велизария тоже поделилась, развернулась и на полном галопе ворвалась в отряды с тыла.
Так случилось, что многие жены вандалов сменили мужей во второй раз. Они оставались в лагере, когда восставшие разбежались по пустыне. Каждый действовал сам за себя. Их ловили солдаты Велизария, а вместе с ними забирали остатки награбленного добра. Больше всего погибло вандалов, потому что как только стало ясно, что Велизарий одержал победу, он приказал своим солдатам не нападать на восставших, которые впоследствии могли снова принести клятву верности. Действительно, тысяча сбежавших солдат мирно сдалась и их помиловали.
Велизарию следовало продолжать преследование и призвать к себе на помощь оставшийся верным гарнизон в Хиппо и войска, расквартированные в Марокко, чтобы до конца подавить восстание. Но он был обычным смертным и не мог одновременно находиться в Сицилии и Африке. От госпожи Антонины только что прибыл гонец с вестями, что начался мятеж в Сиракузах. Велизарию пришлось оставить Хилдиджера, его будущего зятя, временным командующим армии в Африке и вернуться со ста всадниками в Карфаген, а оттуда морем - в Сиракузы.
Как оказалось, солдаты не бунтовали в Сицилии. Там пехотный генерал по имени Константин отказался подчиняться приказам госпожи Антонины в качестве заместителя Велизария. Он заявил, что не собирается подчиняться женщине, кроме императрицы, которой иногда император поручал некоторые важные дела. В соответствии со старым римским законом, женщины не могли быть военачальниками.
