Jean-Pierre Chevènement pose comme préalable de toute négociation la signature d'un texte intitulé « Principes et fondements juridiques régissant les rapports entre les pouvoirs publics et le culte musulman ». Pour le ministre, il s'agit là de « faire confirmer aux signataires leur reconnaissance des lois de la République » et d'affirmer « qu'il n'existe pas de conflits de principe entre la tradition du culte musulman et l'organisation légale des cultes en France ». Le 28 janvier 2000, la quasi-totalité des personnalités et mouvements sollicités acceptent de signer le document. La démarche du ministère de l'Intérieur reçoit ainsi l'aval d'un éventail assez complet de l'islam français : de l'UOIF, très conservatrice, à des personnalités modérées, comme le grand mufti de Marseille, Soheib Bencheikh. Jean-Pierre Chevènement, qui réaffirme que « la République française respecte l'islam comme elle respecte les autres religions », insiste pour que cette « consultation » ne soit pas imposée par l'État mais soit bien le reflet de « l'auto-organisation des musulmans dans le cadre des lois qui sont celles de la République ».

Le gouvernement propose ensuite de travailler sur des sujets qui appellent des solutions concrètes et rapides : création éventuelle d'associations cultuelles, création de nouveaux lieux de culte, ou statut des religieux. Trois groupes de travail associant des experts musulmans, des représentants des différentes administrations concernées et l'Association des maires de France sont ainsi créés. Le départ de Jean-Pierre Chevènement se produit au moment où la consultation est sur le point de déboucher. Les participants adressent d'ailleurs une lettre au gouvernement demandant la poursuite de la démarche engagée. Daniel Vaillant, qui succède à Jean-Pierre Chevènement, s'y engage. Le 3 juillet 2001, le processus marque une avancée de taille : à l'issue de délicates négociations, les partenaires de la consultation aboutissent en effet à la signature d'un accord-cadre sur l'organisation future du culte musulman. L'accord prévoit un système d'élections assez complexe à partir des mosquées et des salles de prière, à l'inverse de la procédure suivie en Belgique, où chaque musulman a la possibilité de voter s'il le souhaite. La future instance représentative trouve également un nom : ce sera le Conseil français du culte musulman (CFCM). Et un statut : celui d'une association loi de 1901.

Ce sont les événements du 11 septembre 2001 qui vont accélérer le processus, alors que 60 % de la population française exprime sa crainte face à l'islam et aux musulmans. De leur côté, ces derniers ressentent et vivent mal l'amalgame latent entre islam et terrorisme. Mais alors même qu'en France les représentants musulmans ont unanimement condamné les attentats perpétrés contre les États-Unis, les événements du 11 septembre donnent des arguments aux adversaires de la consultation. La parole se libère : le grand mufti de Marseille, Soheib Bencheikh, accuse les pouvoirs publics d'être irresponsables et complaisants à l'égard des milieux musulmans les plus fondamentalistes. Il qualifie le Tabligh de « secte » et l'UOIF d'« antichambre de l'islamisme le plus radical ». De son côté, la Mosquée de Paris ne cesse de demander un report des échéances électorales, d'abord fixées au 26 mai 2002, puis au 23 juin 2002, et menace de quitter la consultation. Celle-ci s'enlise donc une nouvelle fois, écartelée entre deux tendances rivales : un islam modéré, originaire d'Afrique du Nord, et un islam transnational qui puise ses sources dans des mouvements fondamentalistes comme celui des Frères musulmans d'Égypte, interdit dans de nombreux pays musulmans.

Nicolas Sarkozy est pressé d'organiser l'islam de France

« La situation des musulmans dans notre pays n'est pas bonne ».

Quand il s'installe place Beauvau en juin 2002, Nicolas Sarkozy hérite du dossier dans un contexte toujours très tendu à l'égard des musulmans. « La situation des musulmans dans notre pays n'est pas bonne », serine le ministre. Il reçoit d'abord individuellement chacun des membres de la consultation, avant de les réunir tous le 20 juin. Le nouveau ministre affirme être prêt à poursuivre le processus de la consultation, tout en acceptant que tout travail accompli puisse être remis en question. Sa méthode : mélanger une part d'élections et une part de cooptation pour faire émerger une future instance représentative équilibrée. Son objectif : qu'aucun courant de pensée ne prenne le pas sur les autres et que les femmes, ainsi que les minorités, soient représentées.

Le séminaire de Nainville-les-Roches

Tout s'accélère encore avec le séminaire de Nainville-les-Roches. Les 19 et 20 décembre, Nicolas Sarkozy réunit les musulmans de la consultation à huis clos au château de Nainville, propriété privée du ministère de l'Intérieur. Le ministre espère parvenir à l'arraché à mettre sur pied une instance représentative de l'islam de France, qui puisse satisfaire les différentes tendances concernées. Le 9 décembre 2002, un premier accord – une sorte de pacte de non-agression – avait été conclu entre les trois principales fédérations (FNMF, Mosquée de Paris et UOIF) pour organiser le futur Conseil français du culte musulman. Dix jours plus tard, derrière les grilles du château de Nainville-les-Roches, les fédérations rivales, les grandes mosquées et les personnalités qualifiées parviennent enfin à se mettre d'accord sur la composition du bureau exécutif du futur CFCM. Il s'agit là d'une avancée considérable. L'élection de Dalil Boubakeur, recteur de la Mosquée de Paris, à la tête du CFCM est désormais admise par tous. Le ministère de l'Intérieur tenait en effet à ce que le CFCM soit présidé par le représentant d'un islam modéré, et implanté en France depuis plusieurs générations, quoique peu représentatif. La FNMF et l'UOIF obtiennent quant à elles les vice-présidences de l'instance représentative. Selon les protagonistes, le séminaire est un succès. Aux yeux de Dalil Boubakeur, l'accord est « historique ». Seule femme supposée siéger au bureau du CFCM, Bétoule Fekkar-Lambiotte démissionne pourtant deux mois plus tard, reprochant à Nicolas Sarkozy de privilégier l'UOIF, qu'elle juge « parfaitement rétrograde ». Bétoule Fekkar-Lambiotte sera remplacée par Dounia Bouzar, membre de la Protection judiciaire de la jeunesse (PJJ) et auteur d'un livre sur les nouveaux prédicateurs musulmans. D'autres détracteurs du CFCM contestent également le choix non démocratique des membres du bureau exécutif du Conseil. D'autres, enfin, insistent sur le fait que l'islam de France, organisé ou pas, reste sous influence des pays d'origine, comme le Maroc ou l'Algérie.

Les élections du CFCM et des CRCM

Le 23 février 2003, c'est en tenue de jogging, à l'issue d'un week-end de discussion place Beauvau, que le ministre de l'Intérieur annonce qu'un accord a enfin été trouvé sur le fonctionnement du Conseil du culte musulman, ainsi que sur l'organisation des élections. Ces dernières sont fixées aux 6 et 13 avril suivants.