השלים את המשפט הבא: אחרי הקריירה הלא מובהקת שלו ברומא כמשפטן ונואם, הוא נכנס לצבא. מסעו הראשון שנרשם היה תחת קוונטוס סרוויליוס קאיפיו ונגמר בקרב אראוסיו בשנת 105 לפנה"ס, שם הוא הראה אומץ יוצא דופן. בשירותו תחת גאיוס מאריוס, סרטוריוס הצליח לרגל אחרי שבטי הגרמנים הנודדים שהביסו את קאיפיון. אחרי ההצלחה הזאת, הוא כמעט בוודאות נלחם בגדול
הקרב באקווה סקסטיה (כיום אקס-אן-פרובנס, צרפת) בשנת 102 לפנה"ס, שבו הובסו באופן מכריע הטוטונים והאמברונים. הוא כנראה גם נלחם בקרב וורצלה בשנת 101 לפנה"ס, שם הובסו הקמבריים באופן מכריע, והסיים את הפלישה הגרמנית. כמה שנים לאחר מלחמות הקימבריה, הפטרון של סרטוריוס, גאיוס מאריוס, נפל מהחסד על תמיכתו בדמגוג לוציוס אפוליוס סאטורנינוס, והוא וסרטוריוס נאלצו לצאת מרומא לזמן מה. סרטוריוס נסע להספניה האולטיורית ושימש את המושל שלה, טיטוס דידיוס, כטריביון צבאי. הוא הבחין בעצמו על ידי כיבוי התקוממות בקסטולו ובסביבתו וזכה בכתר הדשא.