Ces propositions parurent séduire l'Empereur. Les lettres du gouverneur furent soumises à M. Troplong, président du Sénat, chargé de formuler en décrets les mesures qu'elles recommandaient. Ces décrets furent élaborés et même imprimés; ils allaient paraître, lorsque l'Empereur, au moment de les signer, se ravisa et voulut consulter le maréchal Vaillant, ministre de la Guerre; celui-ci combattit les idées de son subordonné et réussit à les faire écarter. La solution qui prévalut fut le rattachement à Paris et la création du ministère de l'Algérie.

L'histoire de l'Algérie sous le Second Empire est essentiellement celle d'un long conflit entre l'élément civil et l'élément militaire. L'affaire Doineau (1856) en fut la manifestation la plus aiguë et contribua à l'aviver. Le capitaine Doineau, chef du bureau arabe de Tlemcen, était, dit du Barail, « un grand gaillard à l'air hardi, qui portait la tête haute et le nez en l'air, bon garçon, cordial, la main ouverte, prêt à rendre service, intelligent, rompu aux finesses de la diplomatie arabe, complètement maître de l'esprit de son général, qui ne voyait que par ses yeux; en somme, agent précieux, mais trop disposé à gagner à la main. » Il y avait entre lui et l'agha des Beni-Snous, Mohammed-ben-Abdallah, une haine farouche, irréconciliable.

Le 12 septembre 1856, à trois heures du matin, l'agha Ben-Abdallah prit la diligence de Tlemcen pour se rendre à Oran. Un quart d'heure environ après être sortie de Tlemcen, la voiture fut entourée par une douzaine de cavaliers portant le costume indigène; les uns suivaient la diligence depuis les abords de la ville, les autres étaient sortis d'un bois d'oliviers qui longeait la route. Des coups de feu se font entendre, les chevaux sont arrêtés, l'agha et son interprète Hamadi, qui occupaient le coupé de la diligence, sont tués à bout portant; un des voyageurs de l'intérieur, M. Valette, est tué aussi par une balle égarée.