Войниците от тази първа по рода си армия, съставена изцяло от пролетарии, сами се кръстиха „мулетата на Марий“, защото пълководецът им ги беше натоварил като мулета. В традиционната римска армия, в чийто състав влизаха само хора със собственост, дори простите войници отиваха винаги на поход, ако не с муле или с магаре, то поне с по един роб, който да им носи багажа. Онези, които не можеха да си позволят лукса да притежават нито едното, нито другото, срещу пари си наемаха място за товар на гърба на чуждото муле или на чуждия роб. Вследствие на това никой не можеше да твърди със сигурност колко каруци се движат заедно с един легион, защото повечето от тях бяха частна собственост и за тях отговаряше само притежателят им. Вследствие, на което пък всяка една „традиционна“ армия се придвижваше много по-бавно и се прегрупираше много по-трудно от африканския корпус на Марий, съставен само от просяци и дрипльовци. Навярно това бе и една от причините в идните шестстотин години Рим да разчита именно на армии от новия тип.
Марий беше дал на пролетариите възможност да вършат нещо полезно и да получават заплата за труда си. Но в желанието си да ги превърне в боеспособна армия, той им направи и куп други услуги, като например тази да отреже горния и долния заоблен край на иначе високите цели пет стъпки римски щитове — толкова големи, че не би могло да се окачат на гърба при всичкия товар, който легионерът трябваше да мъкне със себе си; сега щитовете бяха само три стъпки високи и нито се закачаха за багажа, нито при ходене удряха нещастния пехотинец в глезените.
И така войската се придвижваше в своята десеткилометрова колона право към западните части на Нумидия, войниците пееха с пълно гърло своите бойни песни — хем да изравнят крачка, хем да почувстват какво значи воинска солидарност; всички вървяха заедно, пееха заедно — като една огромна човешка машина, която помиташе всичко по пътя си. По средата на колоната маршируваше самият Марий заедно с целия си щаб, мулетата и каруците, които носеха бойното им снаряжение, и всички заедно пригласяха на войниците; никой от висшите началници не яздеше кон, защото това уморяваше повече от ходенето и ги правеше забележими от километри; за всеки случай обаче всеки от офицерите имаше по едно животно близо да себе си, така че в случай на внезапно нападение генералът да наблюдава сражението от по-високо, а помощниците му — да предават по-бързо заповедите му.
— Всеки град и всяко село, който ни се изпречат, ще бъдат безмилостно оплячкосвани — закани се Марий пред Сула.
И този му план беше грижливо привеждан в действие, още повече, че се оказа практичен — всичко, което се откриеше в хамбарите и складовете с месо, отиваше директно за увеличаване дневната дажба на легионерите, местните жени пък биваха изнасилвани най-вече защото на римляните им домъчняваше за собствените им наложнички в лагера, а проявата на хомосексуални наклонности се наказваше със смърт. Но най-важното бе, че всеки си отваряше очите на четири в търсене на скъпоценности; никой нямаше право да запазва намереното само за себе си, всичко се предаваше на армията.
На всеки осем дни войската почиваше, а случеше ли се някъде по пътя да излезе на морския бряг, Марий даваше право на всеки да се отдаде на три дни плуване, ловене на риба и здраво похапване. В края на май легионите вече бяха подминали Цирта и се насочваха на запад, а в края на квинктидис достигнаха бреговете на река Мулухат, хиляда километра западно от нумидийската столица.
Походът се оказа лек; армията на Югурта така и не посмя да се появи, населението на градовете и селата дори и не помисляше да се съпротивлява срещу римляните, а пък те, благодарение на блестящата организация, скоро свикнаха с особеностите на терена и нито веднъж не останаха без храна или вода. Неведнъж неизбежното меню от сухари, бобена чорба, осолено месо и изсъхнало сирене се разнообразяваше с козе месо, риба, телешко, овче, с плодове и зеленчуци, които неизменно повдигаха духа на войниците, а пък киселото вино, което се предвиждаше от време на време легионерите да пият за сметка на армията, се изместваше от далеч по-пивките винарски постижения на местното население, ако не от типичната за берберите ечемичена бира.