Rómába visszatérve Octavianus Agrippát bízta meg Kr. e. 41-ben a Lucius Antonius és Fulvia Antonia ellen kezdődő perusiai háború vezetésével, amit gyors hadműveletekkel fejezett be Kr. e. 40-ben. Helytartóként Kr. e. 38-ban az aquitaniai törzsek lázadását verte le Galliában, majd átkelt a Rajnán, hogy megtorolja a germán betöréseket. Hazatérve visszautasította a neki megszavazott diadalmenetet, de elfogadta a következő évre (Kr. e. 37.) szóló consulságot.

Ebben az időben Sextus Pompeius szicíliai flottája uralta az itáliai partvidéket. A háború elkerülhetetlen volt, vezetése pedig ismét Agrippa feladata lett. A hadvezér első dolga volt, hogy biztonságos kikötőt hozzon létre hajói számára, amit a Lucrinus-tavat és a tengert elválasztó földterület átvágásával oldott meg.
A Lucrinus-tó és az Avernus-tó összekötésével egy belső és egy külső kikötő létrehozására is módja adódott. Ebben az időbenvette feleségül Pomponia Caecilia Atticát, Cicero barátjának, Titus Pomponius Atticusnak a leányát.

Eleinte Octavianus maga vezette a hadműveleteket Sextus Pompeius ellen, azonban kétszer is vereséget szenvedett Messinánál: először Kr. e. 37-ben, majd Kr. e. 36 nyarán. A kudarcok hatására Octavianus végül Agrippát tette meg a flotta főparancsnokává. Agrippa intenzív kiképzésnek vetette alá a tengerészeket, majd felvette a harcot a szicíliaiakkal.

Erőfeszítései meghozták a várt eredményt: Mylaenél és Naulochusnál is győzelmet aratott. Egy hónap alatt megsemmisítette Pompeius haderejét, amit tengerészeti koronával honoráltak.