Ensimmäiset pataljoonat astuivat palvelukseen Algeriassa syksyllä 1831, ja legioonalaiset pantiin rakentamaan teitä ja kuivaamaan soita. Legioona valtasi Constantinen kaupungin vuonna 1837 ja 1840-luvun lopussa Ranskalla oli hallussaan koko Pohjois-Algeria. Voitolla oli myös hintansa, vuosina 1831–1835 noin 2 000 legioonalaista, eli noin joka kuudes, kuoli lavantautiin tai malariaan.