Chapitre 1
La Redoute prenait de l'importance; il fallait l'aménager et la fortifier davantage. Il est donc décidé en 1856-1857 de remplacer le mur d'enceinte en terre par un mur en pierre dure de 800 mètres de périmètre et de 5 mètres de hauteur. Cette muraille est flanquée de deux portes monumentales: l'une à l'est dite "porte de Tiaret", l'autre à l'ouest dite "porte de Mascara". A la même époque, l'embryon d'hôpital est agrandi et, dans l'ensemble des bâtiments est construit une chapelle. Celle-ci est une vaste salle de 15 mètres de long sur 7 mètres de large surmontée d'un clocheton. Cette chapelle devait servir d'église paroissiale jusqu'en 1904.
La population catholique augmentait chaque jour. Elle réclamait les secours religieux auxquels elle a droit mais le service religieux était assuré par le clergé de Mascara à 75 kms de distance. Le 1er juin 1858 Mgr Pavy, évêque de toute l'Algérie, érigea Saïda en paroisse et nomma comme premier curé M. l'abbé Lacombe. Celui-ci devait assurer le service religieux dans les villages environnants jusqu'à Géryville distant de 200 kms. C'est à ce titre que le 1er mai 1859 M. Lacombe bénit le cimetière de Géryville. M. Lacombe fut installé dans la nouvelle paroisse de Saïda le 20 juin 1858. La construction de la chapelle n'étant pas terminée, il célébra le culte dans les premiers temps dans une salle de l'hôpital et logea à l'hôpital.
Enfin, le 1er novembre 1858 la chapelle fut inaugurée et bénite par le curé lui-même, délégué par Mgr Pavy. La nouvelle paroisse et l'église furent placées sous le vicable de Saint Paul, ermite. Elle débuta avec un maigre budget de 1200 francs que lui alloua le bureau de la Yacouba. Avec cette somme sont achetés un autel en bois peint, des armoires pour la sacristie, un confessionnal en bois et une petite cloche. Celle-ci est bénite solennellement le 5 juin 1859 en présence de toute la population catholique; elle a pour parrain le fils de M. Colomb, commandant supérieur de El Bayad (Géryville) et pour marraine une fille du général Durrieux de Mascara.