On renonça à tout ce qui alourdissait. Au lieu de voitures, on employa des mulets, sur l'utilité desquels Bugeaud a souvent insisté : " Ce qu'il faut pour faire la guerre avec succès, écrivait-il, ce sont des brigades de mulets militairement organisées, afin de ne pas dépendre des habitants du pays, de pouvoir se porter partout avec légèreté et de ne pas charger les soldats comme on le fait. Beaucoup succombent sous le poids et les plus forts ont besoin d'être conduits avec une lenteur telle qu'il est impossible de faire de ces mouvements rapides qui seuls peuvent donner le succès. Des mulets militairement organisés me paraissent être la meilleure base de la guerre d'Afrique. Il faudrait 80 à 100 mulets pour 1 000 hommes; ils porteraient 10 000 rations; les soldats auraient dans de petits sacs une réserve de quatre jours; ce serait donc quatorze jours de vivres, ce qui est très suffisant pour les campagnes que l'on peut faire dans ce pays. " Lorsque les campagnes duraient plus de quinze jours, on se réapprovisionnait dans les postes-magasins. Le sac des hommes ne contint plus que des cartouches et des vivres, la couverture étant roulée sur le sac.

L'habillement fut modifié. Les soldats avaient d'immenses gibernes, suspendues à la chute des reins par un large baudrier, qui, se croisant sur la poitrine avec le baudrier du sabre, formait une croix de Saint-André qui coupait la respiration. La gorge râlait, étranglée par le col en crin et le collet de l'habit droit et agrafé; la tête pliait sous le poids de l'énorme shako conique; Bugeaud donna aux soldats des vêtements larges, remplaça le col par la cravate en cotonnade, le shako par un képi léger et mou. Deux ordonnances royales du 7 décembre 1841 réglementèrent l'organisation de l'infanterie et de la cavalerie indigènes. Les bataillons d'infanterie indigène prirent le nom de tirailleurs indigènes et les spahis furent désormais distincts des chasseurs d'Afrique, comme les tirailleurs des zouaves. Yusuf fut le premier colonel des spahis, qui, en 1845, furent répartis en trois régiments, un par province.

Bugeaud savait parler au soldat et se faire aimer de lui ; vigilant et actif, il s'occupait des moindres détails; on le vit un jour en marche descendre de cheval pour aider un muletier à remettre ses sacs sur le bât retourné.