沒有實權不可能成為真正的權威。詩人懷念的昔日元老院是文官的，同時也是武官的。傳統的羅馬元老院是由通曉軍事的政治家組成。正因為如此，元老院對是否宣戰這樣的重大問題也能作出在軍事上合適的判斷，打勝仗的概率很高。
斯提利科在以往的戰鬥中顯示出了自己在軍事方麵的才能。他不可能一味地懷古，去向百年來從未上過戰場的元老院議員征詢是否能遠征北非。他向元老院要的是自己這個“聯軍總司令”對原本是同僚的“大元帥”吉爾多開戰的大義，要的是名分。尤其是他在羅馬人眼裏是蠻族出身，大義、名分就更為必要。不管怎樣，對手是比汪達爾人早數百年就開始與羅馬人共同戰鬥的摩爾人。
元老院頒布的“公敵”宣言將從側麵支持軍事行動。如果戰爭的對象是公敵，軍隊就可以招募在大農莊幹活的農奴充軍打仗。如果農莊主不願意，就會被課以每個農奴25枚蘇勒德斯金幣作為代償。當然，這個代償金會被作為傭兵費，用來雇用對在羅馬軍中服兵役感興趣的蠻族人。這也是羅馬帝國軍隊中蠻族兵數量增加的原因之一。
對斯提利科的請求，大農莊主占主流的元老院出於這一原因不肯發布“公敵”宣言。大農莊幾乎任何東西都可以自給自足，即使來自北非的進口斷絕，也不會像老百姓那樣受到影響。當然，一旦糧食從市場上消失，就會發生民眾暴動，大農莊就有遭到襲擊的危險。但斯提利科的緊急進口已使市場平靜了下來。
麵對目光狹隘、隻知利己的元老院議員，斯提利科不得不訴諸強硬手段。他請皇帝霍諾裏烏斯從米蘭來到羅馬，在元老院的議會廳發表演說，陳述討伐吉爾多的必要性。十二三歲的少年隻是念念斯提利科寫好的文章而已。這樣就成功地使得遠征北非成為皇帝、元老院也共同參與的舉國軍事行動，而不是斯提利科的個人想法。在皇帝在場的情況下，元老院一致通過了把吉爾多定為“國家公敵”的宣言。
遠征北非並非斯提利科親往。應該說他不能親往更正確。現在，阿拉裏克這個甚至合法取得了大元帥地位的人正帶著西哥特人屬下盤踞在意大利半島附近。在這樣的形勢下，意大利不能沒人。他把遠征軍的指揮權交給了一位最適合代他討伐吉爾多的武將。
這個人是吉爾多的親弟弟馬西澤爾。他在與哥哥吉爾多的爭鬥中敗北，逃到了意大利。傳說兄弟鬩牆的原因是吉爾多為了實現野心，不惜與被打成異端的多納圖主義者聯手，而熱情的天主信徒馬西澤爾反對這樣的做法。因為宗教的摻和，爭端愈發激烈，馬西澤爾的兩個兒子被吉爾多殺死。馬西澤爾不得不亡命意大利。弟弟對哥哥吉爾多的憎惡，又加上兩個兒子的被殺之恨，狂熱天主教徒的宗教熱情支撐著馬西澤爾，要打倒異端多納圖主義者！斯提利科選擇他的理由也在於此。
馬西澤爾率領的討伐軍規模稱不上軍團，士兵隻有5000人。但這5000人不單是作戰高手，還全部是狂熱的天主教信徒。斯提利科選拔這些士兵的意圖很明確。敵方除了天主教士兵以外，還有為數不少的多納圖主義者士兵參戰。派堅信自己是正統基督教徒的天主教徒去，就可以達到分裂敵軍的目的。
這次作戰完美成功。馬西澤爾率領5000兵馬在北非登陸。與之對峙的吉爾多軍人數近乎他的15倍，達7萬人之眾。兩軍在平原上布陣完畢，馬西澤爾獨自一人挺出中軍，大聲喝道：“這是一場正統基督教與異端的戰鬥！”真是一聲定勝負。吉爾多方的天主教徒士兵們扔掉武器，無心戀戰。並非狂熱基督教徒的摩爾人士兵們見狀也腳下不穩，隻想逃跑。全線崩潰了，吉爾多也望風而逃。他不久被抓住，在馬西澤爾麵前被斬首。就這樣，公元398年夏，討伐軍從比薩港出發不到半年，北非便再度回歸西羅馬帝國。
馬西澤爾卻未能作為勝利者進入迦太基城。傳說他在去迦太基城的途中，過橋時墜入河中，因身著沉重盔甲而溺亡。他也是摩爾人，但他反吉爾多，反多納圖主義者。馬西澤爾死後，立即就有別人繼任指揮官。這人不是摩爾人，他事先被斯提利科派去討伐吉爾多。斯提利科還委托他重新整頓吉爾多統治多年的北非。