Pompey joined Metellus in Hispania in 76 BC. While arriving with many expectations, Pompey would prove himself to be more effective that Metellus was. Perhaps it was Sertorius, and not Pompey who was really the pre-eminent commander of the day. From the moment Pompey crossed the Pyrenees, he was harassed and outmaneuvered by Sertorius at every attempt. The year 76 BC was a disaster for the joint commanders and they were forced to withdraw.
The next two campaign seasons resulted in more of the same for Rome's supposed greatest commander, Pompey. Both he and Metellus were repulsed in open attacks, sieges failed, and harassed at every turn by Sertorius' Spaniards. Sertorius' fame and glory grew, and with it his ego. This alone seemed to be the only thing able to stop him, as Pompey proved inept in the overall campaign.
By 73 BC, in the face of Sertorius' mounting successes and growing ego, the wheels started to fall off. Sertorius treated with Cilician Pirates, rebellious slaves in Sicily and even one of Rome's great enemies, Mithridates. Sertorius' chief legate Perperna, along with other supporters were growing concerned over the direction of the Spanish Republic.
Jealousy certainly played a major role, but fear of Sertorius' changing behaviour must have had an impact. By this time, he had developed an almost tyrannical control and his supporters were certainly threatened by this power. A conspiracy was developed, led by Perperna, and Sertorius was assassinated at a feast. Perperna assumed command of the formidable forces, but without Sertorius' charisma the rebellion began to unravel. Pompey finally delivered as a promised and put an end to the war. Perperna's army was lured into a trap and decisively defeated.
Despite never beating Sertorius, Pompey would eventually earn a triumph for the victory. It may not have been deserved for his performance in combat, but he proved himself a formidable administrator. Perperna was captured, and initially offered Pompey volumes of information that would implicate leading people in Rome sympathetic towards or directly involved with Sertorius. Pompey, not only didn't look at the documents, but wisely had them destroyed to prevent further danger of rebellion. Perperna and those senior members of his staff were also executed to prevent any further damage.
In 71 BC, Pompey earned his reputation as a genius in provincial governing. He effectively cleaned up any loose pockets of resistance, and promoted fair and generous terms to native tribes through Spain and southern Gaul. With matters mostly secure in Hispania, Pompey returned to Rome the victor, just as Spartacus, the Thracian gladiator, was running rampant through Italy.