In 81 BC Sulla chose his new son-in-law for the important task of recovering Sicily and Africa. Although Pompey had held no previous senatorial office, he was invested with the rank and imperium of propraetor, and given an army of six legions and a fleet of 120 warships with 800 transport ships. Both men and ships were immediately available: the men from Sulla's own armies and the ships from the fleet Sulla had used to transport them from Greece in 83.
Sicily
Hearing of the size and nature of Pompey's force, Perpenna abandoned the island. Pompey soon installed himself in the western capital of Lilybaeum and started hunting down the Marian leadership. His men caught Carbo on the little island of Cossyra and brought him to Pompey who had him executed. This episode, with many colourful embellishments, was later on used against Pompey and resulted in his opponents calling him the insulting name of adulescentulus carnifex, 'the teenage butcher'.
Africa
The opposition to Sulla in Africa presented a far more serious treat than Carbo and Perpenna. The influence of the great Gaius Marius was still strong there, and many exiled Marian leaders under Domitius had raised a large army of about 27,000 men, supported by a Numidian prince, Hiarbas. They were encamped near the city of Utica. After the execution of Carbo Pompey handed over control of Sicily to his brother-in-law Gaius Memmius and sailed for Africa. He landed his forces in two divisions at Carthage and Utica. Once more size and speed produced an immediate effect: 7,000 Marians defected or deserted. This must probably have been one of the main reasons for Domitius to offer battle before the morale of his men fell even further.
Battle
Domitius marched his army out of his camp and drew up his battle lines behind a ravine, he hoped to entice Pompey into attacking uphill across difficult terrain. A storm broke out and it rained for the better part of the day, Domitius finally decided that there was not going to be a battle and marched his army back to camp. On seeing his enemy march off Pompey ordered his men to attack across the ravine. At the same time the wind had sifted and the rain was driven into the Marian's faces as they turned in disorder to meet the charge. Pompey's seizure of the initiative was a decisive move, his men quickly overcame their adversaries and the battle ended in a complete victory for the Pompeians. The victorious troops hailed their commander as Imperator. No doubt remembering his failures the previous year, when he failed to complete victory by not taking the enemy's camp, Pompey checked the premature celebrations and ordered an immediate assault on the enemy camp. Domitius‘ camp was taken by storm and the enemy commander was killed during the assault. This time Pompey's victory was a complete and total one.
Aftermath
The war in Africa was far from over. To the west the kingdom of Numidia was still in the hands of Hiarbas who was now preparing his country to resist the upcoming invasion. A replacement for Hiarbas was ready to hand in the person of Hiempsal, whom Hiarbas had earlier deposed, and Pompey now embarked on a new campaign aimed at restoring Hiempsal to power. While Pompey advanced into Numidia from the east, Bogud of Mauretania, an ally of Sulla, launched an invasion from the west. Hiarbas was caught between the two and was soon captured and executed. After restoring Hiempsal to the throne Pompey returned to Italy. Within forty days of landing his army at Utica Pompey had returned there to join his fleet. Before returning to Italy the troops hailed Pompey with the cognomenmagnus, 'the Great', for Pompey's childhood hero Alexander of Macedon.