Едва прекратил Помпей наводить порядок в делах Сицилии, как получил от сената декрет, предписывающий ему дела Африки, где сформировалось второе ядро сопротивления вокруг неразоружившегося Гнея Домиция Агенобарба, женившегося, как и Цезарь, на дочери Цинны. Положение в этой провинции было особенно тревожным, и если в общем марианцам удалось установить здесь солидную базу (уже в 88 году Марий и многие другие из его друзей нашли здесь убежище), промагистрат, направленный туда в 82–83 годах как противник Суллы, нашел здесь трагический конец. Нужно сказать, что Гай Фабий Гадриан был особенно одиозной личностью: в продолжение всего своего правления он отличался жадностью и жестокостью настолько, что римские и африканские граждане, устав от лихоимства пропретора и его рабов, осадили их в его резиденции Утик, с которой расправились, предав огню со всеми ее обитателями. Через несколько лет Цицерон утверждал: «Эта смерть казалась такой оправданной, что вызвала общую радость, и не было издано никакого предписания, чтобы наказать ее авторов». Нужно сказать, что в середине 82 года в Риме было чем заняться, кроме как делегировать расследование поджога резиденции пропретора Африки. Домиций, высадившись на континент с остатками консульских армий, стал, так сказать, преемником Фабия Гадриана и занялся организацией солидной армии, перегруппировав 30 000 человек с помощью хотя бы Гиарбаса, которого посадил на трон Ну мидии, согнав с него законного владельца Гимпсала.
Помпей же, оставив Сицилию на попечение своего деверя Гая Меммия, приказал отплыть своим войскам, которые он высадил частично в У тике, частично в Карфагене. Едва он ступил на африканскую землю, как солидный контингент армии Домиция (7 000 человек) перешел на его сторону и встал в его ряды. Очевидно, дела представлялись скорее хорошо. Однако один инцидент произошел во время развертывания лагеря в Карфагене, который указывал на ограниченность власти шефа, будь то сам Помпей: во время земляных работ солдаты обнаружили клад с большим количеством золотых предметов, вероятно, закопанных в момент разрушения пунической столицы в 146 году. Как только распространилась эта новость, солдаты забросили все другие дела, оставаясь глухими к приказам, и принялись рыть равнину, убежденные, что найдут другие клады. Только через несколько дней, устав переворачивать понапрасну землю, они снова вернулись под знамена своих соединений. Неспособный воспрепятствовать повальному стремлению к золоту, Помпей предпочел посмеяться над ним, и только когда восстановился обычный порядок, он принялся за кампанию.
События разворачивались очень быстро: Помпей добрался до Домиция, разбившего свой лагерь под защитой каменистой лощины и рассчитывавшего использовать преимущества своей позиции. Но так как с рассвета разыгралась гроза, Домиций приказал дать сигнал к отступлению, используя наступление противника. Помпей, несмотря на дождь и порывы ветра, приказал пересечь лощину и атаковать: замешательство войск Домиция помешало им эффективно сопротивляться, тем более что ветер и дождь стали для них большой помехой. И опять была резня, во время которой 18 000 солдат Домиция остались на месте. Войска же Помпея приветствовали своего командира званием император. Однако последний заявил, что отказывается от почета до тех пор, пока не будет взят и разрушен лагерь противника. Тотчас вернулись к сражению, чтобы уничтожить 3 000 обороняющихся. Помпей руководил операциями, но он на этот раз снял шлем: видимость была такой плохой, что его чуть не убил свой же солдат, так как, замешкавшись, он не сразу назвал пароль, который спрашивал солдат. Гней Домиций Помпей был взят во время захвата лагеря: его постигла та же участь, что и Карбона, то есть привели в трибунал Помпея, который ознакомил его с эдиктом проскрипций прежде чем обезглавить топором. Его голова была отправлена в Рим.
Благодаря своей победе и сдаче большинства городов, Помпей достаточно глубоко проник на нумидийскую территорию, чтобы напомнить племенам варваров, что Рим намеревается властвовать над всем этим районом. Он восстановил Гипсала на его троне, захватив и убив узурпатора Гиарбаса. И затем, воспользовавшись несколькими мгновениями досуга, он поохотился на львов и слонов: его миссия была завершена раньше, чем кончился 82 год, и возраст его не достиг еще двадцати пяти лет.
Значительной военной силой, способной оказать Сулле серьезное сопротивление, оставалась только армия Сертория в Испании, служившая теперь убежищем для всех проскрибированных, рвущихся продолжить борьбу. Но Испания была далеко и не угрожала Италии ни войной, ни ее снабжением; следовательно, можно было отложить на некоторое время организацию экспедиции (которую Сулла хотел поручить Квинту Цецилию Метеллу Пию), чтобы заняться италийскими проблемами.