En Algérie, où il fut envoyé pour la première fois en 1836, et où il débarqua le 6 juin, le général Bugeaud commença par débloquer un corps de troupes entouré d'Arabes au camp de la Tafna, parcourut le pays dans divers directions, se rendit successivement à Oran, à Tlemsen, et rentra au camp de la Tafna, après avoir deux fois rencontré l'ennemi, auquel il fit éprouver d'assez grades pertes Dans une nouvelle marche sur Tlemsen, dont il allait ravitailler la garnison, il fut attaqué par Abd-el-Kader, au passage de la Sickak, le 9 juillet 1836. Les forces de l'émir s'élevaient à environ 7,000 hommes y compris 1,000 à 1,200 hommes d'infanterie régulière. Acculé à un ravin, ce corps fut mis en complète déroute: 12 à 1,500 Arabes et Kabyles furent mis hors de combat, et 130 hommes de l'infanterie régulière pris vivants. Ces prisonniers, d'une nation peu accoutumée à en faire elle-même, étaient les premiers qui tombèrent en notre pouvoir: traités avec humanité, ils furent transportés à Marseille, et, plus tard, renvoyés à Abd-el-Kader. Cette défaite détacha de l'émir un certain nombre de ses alliés mais ne termina pas la lutte.
Le maréchal Bugeaud.
L'année suivante, le général Bugeaud, qui était revenu siéger à la Chambre des Députes, fut appelé de nouveau au commandement de la division active d'Oran. Prêt à marcher contre l'ennemi, il allait commencer la guerre de dévastation dont il avait menacé les Arabes, lorsque Abd-el-Kader demanda à traiter. Cette ouverture fut accueillie, et le 30 mai 1837 fut signé le traité de la Tafna, grave erreur du négociateur français, comme il l'a plus tard reconnu lui-même avec franchise. Ce traité, en effet, abandonnait à Abd-el-Kader l'administration directe d'une grande partie de l'Algérie et le constituait en quelque sorte le chef de la nationalité arabe. L'émir profita de cette faute avec l'habileté qui le caractérise, organisa le gouvernement des provinces soumises à sa domination et se créa une armée régulière, à la faveur de laquelle il étendit, sa souveraineté, et se mit en mesure de recommencer la lutte qui, engagée en novembre 1839, se poursuit encore avec opiniâtreté en août 1843.
Le lendemain de la conclusion du traité, le général Bugeaud eut avec Abd-el-Kader une entrevue, dont les journaux de l'époque, et notamment le Moniteur du 13 juin 1837, ont reproduit le récit semi-officiel.
Appelé, le 22 janvier 1839, au commandement de la 4e division d'infanterie du corps de rassemblement sur la frontière du nord, attaché ensuite, le 31 janvier 1840, au comité de l'infanterie et de la cavalerie au ministère de la guerre, M, Bugeaud a été nommé gouverneur-général de l'Algérie, par ordonnance royale du 29 décembre 1840, en remplacement de M. le maréchal Valée. Depuis le jour de son arrivée à Alger (22 février 1840), le nouveau général en chef a déployé, dans la conduite des opérations militaires, une activité et une persévérance égales à celles de son infatigable adversaire. Dès le 5 mai, un corps expéditionnaire de 8,000 hommes, qu'il commandait en personne, eut, aux environs de Milianah, un engagement des plus sérieux avec Abd-el-Kader, qui comptait sous ses drapeaux 10 à 12,000 fantassins, soutenus par environ 10,000 cavaliers. L'ennemi, complètement mis en déroute, laissa 400 hommes sur le terrain. Pendant le cours de l'année 1841, Mascara et Tlemsen ont été réoccupés, et les établissements formés par l'émir à Tagdemt, Boghar, Thaza, Saïda, entièrement ruinés et détruits. Les opérations continuées avec non moins de constance, et de succès, en 1842 et 1843, ont considérablement affaibli la puissance matérielle et morale d'Abd-el-Kader, en détachant de sa cause un grand nombre des tribus qui, jusqu'à ces derniers temps, lui étaient restées fidèles et dévouées. Ces résultats heureux sont dus, en partie sans doute, à la vigueur avec laquelle le gouverneur-général a dirigé ses entreprises et conduit la guerre sans se ménager lui-même, tout en veillant avec sollicitude aux besoins et au bien-être de son armée; ils sont dus aussi aux habiles lieutenants qui l'ont secondé, aux généraux Duvivier, La Moricière, Changarnier, Bedeau, Baraguay-d'Hilliers, Randon, aux colonels Cavaignac, Jusuf, Ladmirault, etc., à cette foule d'officiers d'élite, l'orgueil et l'espoir de la France. Mais la meilleure part en revient surtout à nos vaillants et intrépides soldats, toujours prêts à marcher au feu, à braver les périls comme les fatigues et les intempéries du climat, et à sceller de leur sang notre conquête sur le sol africain.
M. le maréchal Bugeaud a publié plusieurs écrits sur l'Algérie: Mémoire sur notre établissement d'Oran par suite de la paix, 1838--De l'Établissement de colons militaires dans les possessions françaises du nord de l'Afrique. 1838.--La Guerre d'Afrique, ou Lettres d'un lieutenant de l'armée à son oncle, vieux soldat de la Révolution et de l'Empire. 1839.--L'Algérie; des moyens de conserver et d'utiliser cette conquête. 1842.
M. le maréchal Bugeaud est le quatrième gouverneur-général de l'Algérie élevé à cette haute dignité militaire. Les gouverneurs-généraux ses prédécesseurs qui ont été revêtus de la même dignité, sont: le comte Clauzel, le comte Valée, le comte Drouet-d'Erlon.
L'année compte maintenant neuf maréchaux: le duc de Dalmatie, nommé le 19 mai 1804; le duc de Reggio, 12 juillet 1809; le comte Molitor, 9 octobre 1825; le comte Gérard, 17 août 1830; le marquis de Grouchy, 19 novembre 1831; le comte Valée, 11 novembre 1837; le comte Horace Sébastiani, 21 octobre 1840; le comte Drouet-d'Erlon, 9 avril 1843, et M. Bugeaud, 31 juillet 1843.