Pagkahuman sa iyang dili-maila nga karera sa Roma ingong usa ka hurado ug usa ka orador, siya misulod sa militar. Ang iyang unang girekord nga kampanya maoy ilalom ni Quintus Servilius Caepio ug natapos sa Gubat sa Arausio sa 105 BC, diin siya nagpakita ug talagsaong kaisog. Nag-alagad ilalom ni Gaius Marius, si Sertorius milampos sa pagpaniid sa naglibot-libot nga mga tribo sa mga Germanic nga nagdaug kang Caepio. Human niining maong kalamposan, seguradong nakig-away siya sa dakong Gubat sa Aquae Sextiae
(karon Aix-en-Provence, Pransiya) sa 102 W.K.P. diin ang mga Teuton ug ang mga Ambrones nadaog sa bug-os. Lagmit siya usab nakig-away sa Gubat sa Vercellae sa 101 BC, diin ang Cimbri nadaog sa bug-os, nga nagtapos sa German nga pagsulong. Pipila ka tuig human sa Cimbric nga mga gubat, ang patron ni Sertorius nga si Gaius Marius nawad-an sa grasya tungod sa iyang pagpaluyo sa demagogo nga si Lucius Appuleius Saturninus ug siya ug si Sertorius kinahanglang mobiya sa Roma sa makadiyot. Si Sertorius mipanaw ngadto sa Hispania Ulterior ug nag-alagad sa gobernador niini, si Titus Didius, ingong usa ka tribuno sa militar. Siya mipalahi sa iyang kaugalingon pinaagi sa pagpugong sa usa ka pagsulong sa sulod ug palibot sa Castulo ug gihatagan sa Grass Crown.