Le mardi 7 août 1956, fut exécuté pour la première fois un condamné à mort par le tribunal permanent des forces armées de Constantine. Mohamed Belkheiria ben Ali, âgé de 23 ans, a été guillotiné à 5h du matin dans l'enceinte de la prison militaire de la Casbah. Né le 12 juillet 1933 au douar Sfahi, commune mixte de Séfia à Souk Ahras, Mohamed Belkheiria séjournera dans la ville de Guelma, avant de rejoindre avec sa famille Constantine où il obtiendra son certificat des études primaires. Après avoir exercé dans le commerce, il sera engagé de force dans l'armée française en dépit de sa santé fragile. Selon ses supérieurs, sa conduite fut correcte. Il fera partie du 15ème bataillon des tirailleurs algériens (BTA) en garnison au camp Fray, au Mansourah. Selon les informations relatées par La Dépêche de Constantine de l'époque, Belkheiria, qualifié de déserteur, avait quitté son unité au début du mois de mars 1956 pour rejoindre un groupe de moudjahidine à Djebel Ouahch. Avec ce groupe, commandé par le chef Salah Boubnider, plus connu par Saout El Arab, il a exécuté plusieurs sorties au cours desquelles il participera à de nombreux attentats contre des fermes coloniales. Le 26 avril 1956 à 19h, une série d'attentats ont été commis dans la ville de Constantine, par un groupe de membres du réseau FLN de Constantine, descendus du maquis de Djebel Ouahch. Au bar Chazot, situé derrière la Grande poste, plus connu après l'indépendance par le café Bosphore, transformé actuellement en bazar, de nombreux consommateurs, dont des militaires et des policiers, étaient accoudés au comptoir. Selon les faits rapportés par le journal La Dépêche de Constantine, certains d'entre eux virent un individu ouvrir la porte et jeter une grenade à l'intérieur. L'auteur poursuivi sera arrêté, alors que son complice réussit à prendre la fuite à travers la rue Bienfait (actuelle Abdelmalek Kitouni). Mohamed Belkheiria sera identifié par les clients du bar Chazot comme étant l'auteur de l'attentat. Il avait été arrêté en possession d'un revolver à barillet de 8mm, selon les services de la police française. Selon les mêmes services, Belkheiria a nié les faits, expliquant qu'il avait pour mission de couvrir son complice, qui a réussi à prendre la fuite. Des révélations qu'ils avaient confirmées lors de sa présentation devant le tribunal, après avoir été terrassé par la maladie en prison. Mais les juges finiront par retenir contre lui les faits de tentative d'assassinat, association de malfaiteurs et port d'armes. Il sera condamné à mort le 18 mai 1956.
