In 1830 nam hij als kapitein deel aan de expeditie in Algerije. Op 15 juni 1840 kreeg hij een kogel in zijn schouder. In 1841 vocht hij de Tagdempt in de slag bij Oued Melah. In 1842 was hij te Chelif en kreeg hij een kogel in zijn rechterarm. In 1843 vocht hij tegen de Flitas. Na enkele jaren bij de état-major te Parijs wordt hij in 1844 weer naar Algerije gestuurd. Hij voerde de Franse linkerflank aan in de slag bij Isly. Hij werd chef van de état-major van de provincie Oran met de graad van luitenant-kolonel.
Op 18 juni 1845 rookte hij de Ouled Fellaha en de Ouled Baaskouna van de Beni-Zeroua uit te Dahara.[1] Vierhonderd mensen, krijgers, maar ook vrouwen, kinderen en bejaarden werden in de bergen van West-Algerije tussen Ténès en Mostaganem achtervolgd door de troepen van Pélissier. Ze verborgen zich in grotten en Pélissier liet brand aansteken, zodat allen omkwamen door verstikking.
Die massamoord lokte verontwaardiging uit in Europa en de minister van oorlog, Nicolas Jean-de-Dieu Soult bood openlijke verontschuldigingen aan. Maarschalk Thomas Robert Bugeaud, gouverneur-generaal van Algerije daarentegen bevorderde Pélissier tot brigadegeneraal.
In 1850 werd hij divisiegeneraal en in mei 1851 werd Pélissier gouverneur-generaal van Algerije, wat hij zeven maanden bleef.
Bij zijn terugkeer in Parijs werd hij senator, werd hij in de adelstand verheven als hertog van Malakoff[2][3] en kreeg hij een jaarlijkse rente van 100.000 francs. Van maart 1858 tot mei 1859 was hij te Londen ambassadeur van Frankrijk bij het Verenigd Koninkrijk.
Hij werd teruggeroepen om het Rijnleger te bevelen.
Sterven in Algerije
In 1860 werd hij opnieuw gouverneur-generaal van Algerije.
In maart 1864 brak een muiterij uit en in mei stierf hij van ouderdom.