Quinto Sertorio era un sabino de Nursia. Sus primeras experiencias militares fueron en el ejército de Mario luchando contra las bandas germánicas de cimbrios y teutones. En el año 90 a. C. comenzó su carrera civil como quaestor en Hispania, a las órdenes de Tito Didio. De vuelta a Roma se vio envuelto en la guerra social. Se encargó de reclutar tropas en la Galia Cisalpina y, durante la revuelta popular, intentó, mediante castigos ejemplares, poner fin a los desmanes de las bandas incontroladas de Mario. En el 88 a. C. aparece ya adscrito al partido "popular" de Mario. Tal vez por no haber podido alcanzar los favores de Sila.