From the time of Sulla's victory in the civil war through to his death, one member of the Marian faction managed to hold on and resist. A member of Cinna's opposition government in the late 80's BC, Quintus Sertorius served as a praetor in 83 BC and was active with Scipio Asiagenus and Norbanus against Sulla in the civil war. Prior to Sulla's victory however, Sertorius was fortunate enough to be appointed as governor of Hispania in late 83 BC. He was able to leave Rome, and avoid Sulla's proscriptions, taking his post by 82 BC.
Sertorius used his distance from Rome, as well as the turmoil that plagued the political system, to begin the concept of an alternative Republic. An obvious opponent to Sulla's plans, the dictator wasted little time in going after him. An army was sent in 81 BC to depose the governor of Hispania, and he prepared to meet it with his mostly Spanish natives. A legate set to meet the Sullan army in the Pyrenees was murdered, however, and Sulla's men took control of Hispania. Sertorius, outnumbered and outclassed, fled to Mauretania in North West Africa to avoid proscription.
His self imposed exile wouldn't last long however. Within the next year, 80 BC, the large and formidable Lusitani tribe had had enough of rule by Sulla's legates. They prompted Sertorius to return to Spain, with the promise of support against his enemies in Rome. He immediately won two victories over the Roman forces, and set himself up in a position of relative security. At some point after his return, along with a great number of Romans who had been victims of Sulla's confiscations or proscription lists, he proceeded to set up Spain as a mirror of Rome. Arranging his own Senate of 300 men, along with all the appropriate elections of quaestors and praetors, Spain quickly turned into a welcome destination for opponents of the Sullan regime.
With a limited number of actual Roman legionaries, Sertorius turned to his Hispania allies for defense of the new Republic. Large numbers of recruits were gathered and trained in the Roman style. These recruits pledged loyalty directly to Sertorius, rather than the government, as this was the custom in the native tribes. Sons of tribal leaders were brought to the capital to serve both as hostages against revolts, but also to receive formal Roman educations. He adopted a white fawn, keeping it with him as a pet, as the natives believed this to be a token of favor from the gods. He played brilliantly upon the Celt and Iberian cultures in order to ingratiate himself with them. Ultimately, the success of this fledgling 'Spanish' state depended entirely on the success and charisma of Sertorius, but it started with much promise. If nothing else, despite his opposition to the Sullan government in Rome, his measures in Hispania went a long way towards romanizing the native tribes.
By 80 BC, the Senate was forced to take action. Q. Caecilius Metellus Pius, another Sullan general, was commissioned to end the rebellion in Hispania. 79 BC, however, didn't go Metellus' way at all. Sertorius was a brilliant commander and knew how to use his Spanish troops effectively against Roman tactics. Despite their Roman training, his tribal forces were used in a guerrilla faction, disrupting and irritating the enemy where possible, and avoiding major confrontation on open land except where unavoidable. Using these tactics, Sertorius inflicted 3 major defeats on Metellus in the year 79 BC alone.
Back in Rome, news of the defeats was compounded with more internal problems. Pompey had refused to disband his army after his victory over Lepidus, and matters were looking more and more like a repeat of previous holds on power through military force. Pompey, however, wasn't interested in power within the city. He wanted the command in Spain and used the threat of his veteran legions to get it. Despite the fact that it was technically illegal for Pompey to hold a command in the first place, pro consul L. Marcius Philippus finally proposed for Pompey to have the command. In a time of massive ignoring or blatant disregard for the constitution, it was no surprise that in order to avoid a military confrontation; the command was given to Pompey. Before Pompey's arrival however, Sertorius was reinforced by the remains of Lepidus army, under Perperna, in Sardinia. His additions made Sertorius even more of a formidable foe.