Gallien, år 50 før Kristi fødsel.
Obelix forelsker sig i Lillefix, men hun er forlovet med Tragicomix, der er udskrevet som romersk soldat og på vej til Afrika. Asterix og Obelix drager ud for at finde ham. Undervejs støder de på henrivende eksempler på romersk bureaukrati med kontorer, der henviser til andre kontorer ad infinitum.
De melder sig til hæren og møder medrekrutterne Demagogos fra Grækenland, Sølax fra England, Jovilix som er flamlænder, Tårnur og Sekstur der er gotere og Tennis, der er ægypter. Endelig er der en tolk med mange talenter. Centurionen - Quousque Tandem - bliver som forventet hylet noget ud af den. Maden er under al kritik, så kun englænderen nyder den. Asterix taler lidt med kokken og foplejningen bliver nu tip-top.
Rekrutterne overgår til kommando af Sergent Patientia Nostra, af første legion, tredie kohorte, anden manipel, første centurie.
På stroppeturen bærer Asterix og Obelix alle kammeraternes rygsække og løber i forvejen, så Patientia ikke kan følge med.
Afrejsen til Afrika fra Massilia foregår i civilt "det er mere praktisk" og med officererne halsende bagefter. Galejen møder sørøverne og det går som ventet sørøverne ilde. Vel ankommet til Afrika leder Asterix og Obelix forgæves efter Tragicomix, for han er savnet efter et sammenstød med Scipios styrker.
Spionen, KCN, hvis rigtige navn Cyankalium er hemmeligt, fortæller at Tragicomix er fange. Asterix og Obelix befrier ham, men sætter samtidig gang i et angreb, som Cæsar vinder. Som tak tilstår han dem en gunstbevisning og de tager hjem sammen med Tragicomix. Undervejs går det ud over sørøverne en gang til.
Vel hjemme tager Lillefix og Tragicomix afsted for at starte en græsrodsbevægelse, men Lillefix giver Asterix et kys på næsen, så han tilbringer festen i en lille lyserød sky oppe i et træ, mens de andre - undtagen Trubadurix - fester igennem.
Ganske morsom fortælling, der veloplagt knytter flere tråde sammen - militær - bureaukrati - kærlighed. ( )