Tous ceux parmi les Constantinois qui ont vécu la guerre de libération, notamment les habitants des quartiers populaires de Djezzarine, Rahbet Essouf, Rcif et la Casbah se rappellent encore à ce jour du fameux attentat survenu le samedi 12 mai 1956 à la rue Sidi Lakhdar. «C'était le deuxième jour de l'Aïd Seghir ; nous étions de passage par la rue de France vers 12h30, quand nous avions entendu le bruit d'une déflagration du côté de la rue Sidi Lakhdar suivie d'une fusillade ; c'était la grande panique parmi la foule ; nous avons appris que deux individus ont lancé une grenade à l'intérieur du bar Mazia, tenu par un juif appelé Sebbah, situé non loin de la rue de France», nous raconte Saïd B., qui avait 16 ans à l'époque. L'attentat, qui a surpris les clients de ce bar, est le second en l'espace de deux mois, mais cette fois-ci les dégâts humains et matériels sont plus importants. Selon les faits rapportés par la Dépêche de Constantine du lundi 14 mai 1956, l'engin a causé des blessures à 13 consommateurs, tous des juifs, attablés dans ce bar en ce jour du Sabbat. Certains ont été évacués vers l'hôpital dans un état grave. Presque au même moment, un autre attentat a été perpétré à la rue des Cigognes, une artère parallèle à la rue Sidi Lakhdar, et qui descend vers la place de Rahbet Essouf. Une fois l'alerte donnée, un accrochage a eu lieu entre les membres du commando du FLN et les forces de l'ordre dans cette partie de la ville. Trois policiers ont été blessés. Parallèlement à cet attentat, des fusillades ont été signalées à la rue Thiers (actuelle rue Tatache Belkacem), à la Casbah, au dessous du pont Sidi Rached, et à la rue Bienfait (actuelle rue Kitouni). Le bilan est important, selon les autorités militaires françaises qui ont avancé le chiffre de 12 morts et 30 blessés, dont les 13 clients du bar Mazia. Les mêmes sources ont signalé qu'après une chasse aux auteurs des attentats, six membres du commando ont été tués et quatre autres blessés. Les attaques du 12 mai 1956, sont, de l'aveu même des autorités françaises, les plus importantes depuis les évènements du 20 août 1955. Le général Noiret, commandant la Division et les troupes de l'Est algérien a suivi lui-même le déploiement du dispositif militaire, accompagné de son adjoint le général Giraud. Ces attaques ont été suivies d'une grande opération militaire, marquée par des rafles et des arrestations. Des témoins se rappellent de ces dizaines de personnes amenées au centre d'interrogatoire des services de sécurité. Des Constantinois se rappellent encore des tueries commises en représailles contre les musulmans le 19 mai 1956 dans l'ex-rue Chevalier (aujourd'hui rue du 12 mai 1956). Des actes que le FLN avait imputés aux services de la DST.
