In 88 BC, Lucius Cornelius Sulla marched his legions on Rome, starting a series of civil wars. After Sulla took the city he murdered a number of his political opponents and secured the exile of Gaius Marius, his main rival. In 87 BC Sulla left for the east to fight Mithridates VI of Pontus (see: First Mithridatic War), Lucius Cornelius Cinna one of the new consuls turned against Sulla and together with Marius who had returned from exile he recovered Italy from the Sullan faction. When Sulla returned in 83 BC his main opponents had already died (Marius in 86, Cinna in 84) but he still had to fight a fierce civil war against Marius' faction (called the Marians). After Sulla's victory at the Battle of the Colline Gate the Marian resistance in Italy crumbled. Sulla's remaining opponents were either killed or fled.

Papirius Carbo, the Marian consul, fled to Sicily which was being held for the Marians by Marcus Perperna. Gnaeus Domitius Ahenobarbus who had already fled to Africa before the fall of Italy was in the process of building an army near Utica. Quintus Sertorius held the Roman provinces on the Iberian peninsula and was also building up his forces. Sulla now started the next phase of the war by sending out his armies to hunt down his remaining enemies.

In 81 BC, Sulla chose his new son-in-law (Pompey was married to his step-daughter Aemilia) 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.^[1]

Hearing of the size and nature of Pompey's force, Perpenna abandoned the island (no military action is recorded). 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 (today Pantellaria) and brought him to Pompey who had him executed (probably on Sulla's orders). 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'.^[2]

The opposition to Sulla in Africa presented a far more serious threat 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.^[3]

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.

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.^[3]

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. The enemy army was destroyed; 17,000 men were killed or captured, 3,000 escaped and scattered.^[3] This time Pompey's victory was a complete and total one.^[3]

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.^[4]

Before returning to Italy the troops hailed Pompey with the cognomen magnus, 'the Great', for Pompey's childhood hero Alexander of Macedon.^[5]