Cette guerre, encore pudiquement appelée « évènements d’Algérie » ou « opération de maintien de l’ordre », va révéler sa vraie nature à la France entière le 18 mai 1956 lors de l’embuscade dite de Palestro. En quelques heures, une section entière est décimée alors que le 9 RIC n’est en grande Kabylie que depuis un mois. Le régiment continue cependant avec opiniâtreté les opérations de reconquête du terrain, d’aide à la population et bien sûr de combat face à la rébellion armée, menée par le Front de libération nationale (FLN).

Avec la montée des tensions, la France cherche à conserver son autorité sur l’Algérie et réorganise plusieurs régiments. Le 9 RIC devient alors le 9 régiment d’infanterie de marine (9 RIMa) en 1959, avec des effectifs renforcés et des unités spécialisées. Si l’économie locale progresse et le commerce fonctionne, la fracture entre Algériens et Européens se fait de plus en plus ressentir. La cause de la rébellion commence même à être entendue sur le plan international et la signature des accords d’Évian est une réalité au jour du 19 mars 1962. Ces accords initient le déménagement du régiment vers Alger afin de remplir une double mission de sécurisation de sites et de maintien de l’ordre. Le régiment connaît son dernier accrochage le 9 avril 1962 contre des membres de l’ALN, sans perte ni blessé chez les marsouins.

Officiellement dissous le 10 avril 1963 en tant que régiment, il se transforme en bataillon d’infanterie de marine (BIMa) au même numéro d’ordre. Toujours présent en Algérie, le 9 BIMa participe à la sécurisation de points sensibles et renoue avec les activités traditionnelles d’entraînement d’un régiment. Le sport, quelque peu délaissé lors des périodes d’engagements opérationnels intenses, reprend de l’importance et le régiment brille dans diverses compétitions locales civiles ou militaires. Le 14 juin 1964, les derniers éléments du 9 quittent définitivement Alger pour Perpignan. Il est de fait la dernière unité des troupes de marine à quitter l’Algérie. Le 30 juin 1964, le 9 de marine est dissous pour la seconde fois de son histoire.