During Spartacus's revolt, he'd defeated Roman armies barring the way into northern Italy and Gaul and could have left Italy entirely.
http://en.wikipedia.org/wiki/Third_Servile_War
However, for reasons unknown, the slave army went south and became trapped in southern Italy. There was an attempt to get some pirates to carry them to Sicily and organize a slave revolt there, but that failed.
Soo....
Some ideas:
1. After defeating the Romans at Mutina, the slave army keeps going north into Gaul. Wikipedia suggests the slaves would be dispersed to where they came from originally, but given how Spartacus was apparently from Dacia and I imagine the slaves would have come from all over, that would be kind of hard. Plus the Romans might hunt for the escaped slaves, who would not have the numbers to defend themselves.
(Of course, this is before the Gallic War, so the Romans would have only controlled part of Gaul and sending soldiers into Gaul to hunt slaves would have started another war.)
2. The pirates don't betray the slaves or the slaves manage to build their own ships and cross to Sicily. Sicily was a powder-keg of abused slaves and corrupt governance, but in prior discussion on the board, someone tried to make the point that Sicily would not be defensible--there were too many potential landing sites to defend.
3. The slaves get transported to Asia Minor and link up with Mithridates. This would require the Cicilian pirates, since building one's own rafts and ships to cross to Sicily is one thing, but crossing to Asia Minor is something else entirely.
4. Other options.
I posted this story here in 2006:
http://www.asimovs.com/_issue_0501/gladiatorswar.shtml
A different Third Servile War that features a lot of the gladiators escaping to help Mithridates, while the rest get into Spain somehow and there's a gotterdamurung there where everybody dies. Of course, it also features Spartacus burning Rome, which is...tricky.