Date : mardi 7 août 1956. Lieu : prison de La Casbah à Constantine. Le fait est la première exécution d'un condamné à mort par le tribunal permanent des forces armées de Constantine. Il s'agit de Mohamed Belkheiria Ben Ali, âgé de 23 ans, guillotiné à 5h du matin dans l'enceinte de la prison militaire de La Casbah. Une exécution qui survient 49 jours après celles d'Ahmed Zabana et d'Abdelkader Ferradj, le 19 juin à la prison de Serkadji à Alger. Ce fait tombé dans l'oubli avait été pourtant très médiatisé par la presse coloniale. Il avait fait la Une de La Dépêche de Constantine du mercredi 8 août 1956. Né le 12 juillet 1933 au douar Sfahi, commune mixte de Séfia à Souk Ahras, Mohamed Belkheiria a été engagé dans les rangs de l'armée française pour servir en Indochine. Il fera partie du 15e Bataillon des tirailleurs algériens (BTA) au camp Fray, au Mansourah dans la ville de Constantine. Selon La Dépêche de Constantine, Belkheiria, qualifié de déserteur, avait quitté son unité pour rejoindre un groupe de moudjahidine à Djebel Ouahch. Avec ce groupe, commandé par Salah Boubnider, plus connu par Saout El Arab, il a participé à de nombreux attentats contre des fermes coloniales. Le 26 avril 1956 à 19h, une série d'attentats a été commise à Constantine par des membres du réseau FLN, descendus du maquis de Djebel Ouahch. Au bar Chazot, situé derrière la Grande Poste de Constantine, plus connu après l'indépendance par le Café Bosphore, transformé actuellement en bazar, un individu jette une grenade à l'intérieur. L'auteur poursuivi sera arrêté, alors que son complice réussit à prendre la fuite par la rue Bienfait (actuelle Abdelmalek Kitouni). Belkheiria Mohamed 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 8 mm, selon 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 confirmées 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 16 mai 1956.
