S'exprimant dimanche 2 décembre pour l'agence de presse algérienne APS, Nicolas Sarkozy a déclaré que "bien sûr, il y a l'histoire, qui est là et continue parfois à s'interposer entre nous. Il ne faut pas l'ignorer mais l'assumer. Cela demandera encore un peu de temps de part et d'autre, car il y a des blessures, des deux côtés, qui ne sont pas refermées. Mais on peut progresser et je suis sûr que, pas à pas, nous pourrons rapprocher notre lecture de l'histoire et réconcilier nos mémoires", avant d'ajouter que "chacun doit faire sa part" dans la voie de la réconciliation.

En visite d'Etat pour trois jours, le président français devrait rencontrer des étudiants à l'université Mentouri de Constantine, mais aussi signer "à la fois les contrats gaziers qui garantiront notre approvisionnement jusqu'en 2019 et un accord de coopération nucléaire", comme il l'a lui-même précisé lors de son interview accordée à l'APS.

Mais le voyage de Nicolas Sarkozy en Algérie ne s'annonce pas de tout repos, puisque son image de l'autre côté de la Méditerranée est sérieusement écornée, d'abord en raison de sa détestation de cette "mode exécrable de la repentance" qu'il voit comme une "détestation de la France et de son histoire", comme il l'a martelé maintes fois durant sa campagne présidentielle, mais aussi en raison de sa politique d'immigration limitant considérablement la délivrance de visas (120 000 auraient ainsi été délivrés en 2006 contre 270 000 en 2001) et de sa mise en place d'un ministère de l'Immigration et de l'Identité nationale.

Le quotidien français Le Monde rapporte ainsi les propos d'un proche du président algérien Bouteflika qui estime que "d'une certaine façon, [il est] l'otage de son électorat et de ses déclarations passées", et que "le langage de M. Sarkozy nous a toujours heurtés. Ses expressions sont ressenties comme brutales. Il choque la population algérienne. Peut-être ne l'avait-il jamais mesuré jusqu'à présent."

Par ailleurs, une semaine avant ce voyage présidentiel, le ministre algérien aux Anciens combattants a déclaré dans le quotidien algérien Al Khabar : "Vous connaissez les origines du président de la France et vous savez quelles sont les parties qui l'ont amené au pouvoir", estimant que "le lobby juif" serait le "véritable architecte de l'ascension de Sarkozy au pouvoir". Le ministre a par la suite été désavoué par le président Abdelaziz Bouteflika, qui a déclaré vouloir accueillir Nicolas Sarkozy "en ami".

Dans son interview à l'agence de presse algérienne APS, M. Sarkozy a pour sa part déclaré : "Je pense que nous devons nous tourner d'abord vers l'avenir, car les nouvelles générations, qui forment dans votre pays la grande majorité de la population, ne vont pas attendre que les adultes aient fini de régler les problèmes du passé."