Le 7 avril 1958, Jacques Lefort entend mener "sa boutique" à son rythme, "c'est à dire infernal !" Dès Ie 26 le régiment reprend ses "roulettes" et fonce vers le secteur d'El-Milia qu'il connaît si bien. Chaque djebel lui est familier, chaque maqui , chaque rocher.
Partis dans la nuit de Philippeville, les légionnaires débarquent dans le froid du petit matin, a Oum -Toub - Happés aussitôt par les bananes du DIH de service. Pour les fellaghas, El-Milia est une zone de concentration des bandes qui ont réussi à franchir le barrage. De là, elles rejoignent les willayas où elles ont été affectées. Au plan topographique, le terrain se présente sous la forme d'une dorsale dont les sommets s'étagent de 700 a 1000 mètres orientée est - ouest et encadrée aux lignes de crêtes parallèles hautes de 700 à 800 mètres au nord, et de 400 mètres au sud. II est évident que cette orientation favorise la pénétration a l'intérieur des katibas.

Pour l'heure, ce sont des "faïleks" que l'ALN lance dans la bataille des frontières. Or là, la malchance veut que les bandes rebelles se heurtent au 2e REP. Les compagnies sont héliportées sur les crêtes des Beni-Sbihi. Un peu plus tôt, l'aviation a fait place nette à la roquette et à la bombe, ce qui permet un "poser" sans casse. D'est en ouest les compagnies sont déployées de la manière suivante : la "4" du capitaine Chollet, la "1ère" du capitaine Fayette, la "2"du capitaine Marce, la compagnie portée du capitaine Bourgin, la "3" du capitaine Coiquaud.

Le PC du colonel Lefort et les appuis installés sur le versant ouest du Kom-Bou-Takouk. Les unités s'apprêtent à ratisser le terrain quand un observateur de Bourgin signale une vingtaine d'hommes sur le Ka-Sottara. Une patrouille envoyée reconnaitre la position se heurte à une résistance organisée et disposant d'armes automatiques. Lefort qui sent ces choses là, voit dans ce le flanc garde d'un ennemi beaucoup plus nombreux Il demande au commandant de l'opération la permission de chasser les rebelles. Sans attendre, il fait boucler le Ka-Sottara. II faut aller vite, si les fellagahs jouent le piège, ils peuvent éclater vers le Nord. La mise en place du dispositif se fait au pas de charge. A midi, toutes les unités sont en place et attendent les rebelles.

La première, la compagnie Marce éprouve le feu ennemi, puis c'est la compagnie portée qui repousse la tentative de passage en force. Coiqaud et Chollet sont au contact.
Quand à Fayette, il attend l'appui d'un peloton de chars, après une préparation d'artillerie et de mortiers de la CA, Chollet et Fayette lancent leurs unités contre les positions de l'ALN. Pendant un quart d'heure la fusillade fait rage, les légionnaires lancent des greandes et tirent de courtes rafales qui atteignent leurs cibles. A 19 heures, les derniers coups de feu retentissent. Le 27, l'aube se lève sur un des plu beaux bilans de la guerre d'Algérie ; à faire pâlir d'envie les Jeanpierre, Bigeard, Buchoud et autres Fossey-François : 199 HLL tués, autant d'armes individueIles récupérées auxquelles il faut ajouter 3 mitrailleuses et 4 fusils-mitrailleurs.
Moins de deux jours plus tard, le 2e REP participe à bataille de Souk-Ahras. Empêchés de commémorer Camerone comme il convient, les légionnaires vont faire la fête ""ux fells". Un nouveau franchissement se produit dans la nuit du 30 avril au 1er Mai. Le REP qui est arrivé de Philippeville dans l'affaire du djebel Mouadjene à son compte et remporte un beau succès.

Au mois le 2e REP quitte Philippeville, pour relever a Guelma le 1 er REP durement éprouvé par la mort de son colonel et de nombreuses pertes.

Le 9 juin 1958, le chef de bataillon Morin qui commande provisoirement le 1er REP passe les dernières consignes à l'état-major du 2e REP. A son habitude, "Toto"est déjà parti renifler le terrain. La ville doit sa célébrité aux récents combats qui ont vu l'anéantissement du "corps de bataille" de l'ALN. Jusqu'à l'arrivée du 1 er REP, l'OPA fonctionnait à merveille et le FLN "dictait sa loi". Les hommes de Jeanpierre se sont chargés de lui rappeler douloureusement qu'il n'y en avait qu'une, celle de la France. Aussi, les bérets verts sont-ils admirés par une partie de la population et craints par l'autre.

C'est dans ce contexte que les légionnaires du 2e REP reprennent à leur compte les missions de leurs prédécesseurs. Le régiment n'est pas en terre inconnue ; plusieurs séjours dans les parages, le dernier tout récemment à Souk-Ahras, ont assis sa réputation. Mais à la différence du mois d'avril, des jours entiers se passent sans que rien ne bouge. On sent l'ALN au bout du rouleau ; les accrochages se font de plus en plus rares. Les longues marches dans les djebels remplacent l'ivresse des combats. Les Beni-Mezzeline, en particulier, subissent de fréquents et importants ratissages.
Dans cette région au relief accusé où chaque "chabet" se transforme en refuge impénétrable, les rares rebelles rencontrés se défendent avec l'énergie du désespoir. Sur le terrain, bien souvent, l'urgence du combat fait que les légionnaires retrouvent les gestes des pionniers du génie-combat : "piéger des mechtas", miner des chemins de montagne empruntés par les rebelles, et parfois, lors de bouclages et de ratissages, débusquer les rebelles camouflés dans les nombreuses grottes des Aurès ou de Kabylie. Un boulot difficile qui s'effectue le plus souvent dans l'obscurité et l'humidité des eaux résurgentes.
Le "commando-grotte" ne peut s'empêcher d'éprouver un réel sentiment de claustrophobie et d'appréhender les pièges mortels à l'approche du gouffre menaçant. La "guerre des grottes" coûte cher et, par exemple, si l'on estime que 25 rebelles ont péri dans l'explosion de celle du Chaba-El-M'Klimene, 8 légionnaires, dont le lieutenant Gastaud, ont succombé à l'inhalation de gaz résiduels. Le major Roos qui eut l'occasion de participer à ce type d'opération n'a jamais oublié
"La pire expérience, je l'ai connue avec mon groupe dans une grotte du côté de Guelma en 1958. Après y être entrés sans difficulté, le boyau suintant et noir s'est rétréci au point de nous obliger à ramper avec les lampes torches pour seule lumière, mais qui constituaient aussi des cibles idéales dans cet espace restreint où l'on remue difficilement.
Nous savions qu'il y avait du fell. Après un labyrinthe, une caverne. Soudain, au détour d'un coude, un tir nous a bloqués dans le tuyau. J'ai parlementé, mais ils ne voulaient pas se rendre. Le décrochage a été difficile ; nous sommes ressortis en lançant quelques grenades. Nous étions bien contents d'être entiers et à l'air libre. II y avait des légionnaires qui "aimaient" ce travail , moi ce n'était pas mon truc" .

Nous avons bloqué la grotte après avoir vérifié qu'il n'y avait pas d'autre issue, puis le Génie est arrivé. Les sapeurs ont entassé du TNT et ont tout fait sauter.
"Vraiment une sale mort !"
Parallèlement à ces activités opérationnelles, le 2e REP mène une action psychologique intense qui permet de détruire l'OPA et déstabilise ainsi le FLN. Le 28 septembre 1958, à Guelma et dans les douars avoisinants, le référendum sur la Constitution se déroule dans le calme le plus absolu. La vie économique reprend et les marchés les plus reculés du bled drainent une population confiante dans l'ordre rétabli par les légionnaires ; ceux-ci n'étant pas les derniers à acheter dans le commerce local pour l'ordinaire et le foyer. La pacification occupe une bonne partie de l'été et de l'automne ; saignée à blanc, l'ALN de Tunisie tente de se reconstituer vaille que vaille. Plus jamais cette force ne représentera une menace ; les bandes tentent de franchir le barrage par petits paquets qui sont impitoyablement anéantis. Dans cette région montagneuse des Aurès, l'hiver est synonyme de courtes journées de brouillard glacé et d'humidité permanente. Le blizzard balaie les crêtes, transperçant les légionnaires. Le plafond, au plus bas, interdit toute activité aérienne. Les pistes ravinées où les camions s'embourbent sont impraticables. Et pourtant, l'activité opérationnelle ne ralentit pas pour autant "Les fells doivent constamment ressentir la menace qui pèse sur eux". Aussi, l'activité opérationnelle du régiment ne faiblit pas : djebel Mahouna, djebel Mahres, El-Milia, environs de Guelma... encore 73 HLL hors de combat à la fin de 1958.
Avec les beaux jours de 1959, les opérations reprennent de plus belle. Le 1er mars, après un court séjour au camp Pehau à Philippeville. le 2e REP revient à Souk-Ahras fouiller le maquis, en l'occurrence ke douar Ouillen qui présente toutes les caractéristiques d'un traquenard.

C'est au tour du capitaine Bourgin de "faire l'ouverture" et de fouiller l'oued Berrik. Devant sa jeep, le 4X4 d'une batterie d'artillerie saute sur une mine. Bourgin fait donner les premiers secours aux blessés, puis il prend la tête de la colonne pour vaincre l'appréhension compréhensible des "conduc teurs appelés". Arrivé sur la zone dangereuse, il fait débarquer sa compagnie et l'engage sur le mouvement de terrain à fouiller. A 150 mètres d'une mechta, la section du lieutenant Bonneton est prise à parte par des rebelles bien camouflés. Le capitaine fixe l'ennemi par le feu de sa section de commandement, puis il ordonne au lieutenant Dorr de prendre les fellalaghas à revers. Pendant que les sections maneuvrent par le Nord, Bourgin, facilement repérable par les antennes de ses radios, reste debout, guidant ses tireurs, désignant les objectifs dans les amas rocheux. La section Dorr est au contact quand soudain, le capitaine chancelle et tombe. Aucun doute possible, le capitaine Bourgin a été touché et sa blessure est des plus mauvaises qui soit : une balle dum-dum dans la poitrine, celles qui ne pardonnent pas.

A 14H30, Bourgin expire : von Palaïeff rejoint Seegers et les autres au Parnasse des Légionnaires. Le lieutenant Dorr prend le combat à son compte. Une balle coupe la courroie de ses jumelles ! Fous de rage, les légionnaires se lancent à l'assaut des rebelles. Deux sont tués, mais à 15H45, les 9 rebelles gisent morts sur leurs positions. II n'y a pas eu de quartier. Un fusil-mitrailleur et 6 armes de guerre tombent entre mains de la CP. Au total, le 2e REP déplore 3 tué 3 blessés pour 46 HLL tués et 2 prisonniers. Plus de 40 armes sont récupérées dont des mortiers.

Bien que basé à Guelma, le 2e REP n'y séjourne guére, les opérations se succèdent, sans grand succès ; l'époque des bilans fabuleux est révolue. L'orgeuilleuse ALN est ramenée à sa condition précaire de bandes plus ou moins contrôlées et dont les chefs se taillent de petits fiefs en organisant leur propre guerre. Aussi tombent-ils les uns après les autres à l'exemple d'Amirouche dont les paras du 6ème RPIMA diront après l'avoir mis hors de combat "Il est mort comme un chacal"

Néamoins, les légionnaires-parachutistes fouillent consencieusement les djebels : beaucoup de sueur, peu de chose comme en témoigne cet extrait de l'article de Képi-Blanc 16 mai (1959),

Le 16 Mai 1959 une opération est montée pour nettoyer le Pain-de-Sucre. Dès 02H30, le brouillard s'est heureusement dissipé. Bientôt, le sous-bois engloutit une à une les compagnies. Une douzaine de kilomètres à parcourir dans une obscurité totale, sur une piste semée d'embûches. Au petit jour, la piste est abandonnée et les unités s'enfoncent profondément dans le maquis. L'emploi du coupe-coupe est nécessaire. Les épineux s'accrochent rageusement aux tenues de combat ; nous avançons lentement. Mais la mer est proche et nous ne sommes plus qu'à trois kilomètres de ce fameux Pain-de-Sucre. Le ratissage commence en direction de la mer. Les compagnies ont encerclé l'imposant rocher. II va être traité par les B 26 et les T 6. Un premier piqué et, quelques secondes plus tard, une épaisse fumée blanche s'élève du rocher. Après quelques passages acrobatiques, la chasse s'éloigne, cédant la place au piper d'observation. Peu après, une compagnie va fouiller le Pain-de-Sucre. C'est a une belle partie d'ecalade, a laquelle l'a convié le commandement

1-2-3-5-6-7-8-9-10-11-12