Dès 1956, de multiples tentatives de contacts entre les belligérants sont menées par divers intermédiaires au nord et au sud de la Méditerranée (70). La Suisse, comme lieu d'entretiens ou comme intermédiaire pour les organiser, est mentionnée dans les conditions suivantes :

En septembre 1958, après la proclamation au Caire de la formation du gouvernement provisoire de la République algérienne (GPRA), le DPF demande à ses collaborateurs d'éviter, dans la mesure du possible, tous contacts avec ce gouvernement que, dans l'état actuel des choses, le Conseil fédéral ne saurait reconnaître (71).
Toutefois, le président du GPRA, Ferhat Abbas, vient en Suisse à de nombreuses reprises. En novembre 1958, il expose à un inspecteur du MPF sa conviction que les négociations avec le gouvernement français sont nécessaires et que le général de Gaulle devrait les accepter avant d'être débordé par les extrémistes de droite ou confronté à une rébellion algérienne soutenue par les Etats communistes. "Ferhat Abbas et ses amis du FLN renonceraient aux bons offices de la Tunisie et du Maroc et préféreraient que les négociations se fassent dans un pays neutre, en Suisse si possible, et ceci sans avoir recours à l'intervention des Nations Unies.(72)" Le DPF prend note de cette proposition, mais ne prend pas d'initiative afin de nouer des contacts avec la France.

En avril 1959, F. Abbas manifeste le souhait de rencontrer un diplomate suisse au Caire. L'ambassadeur de Suisse, Jean-Louis Pahud délègue un collaborateur auprès du président du GPRA qui croit savoir que de Gaulle serait favorable à des négociations qui pourraient avoir lieu en Suisse ou en Espagne. F. Abbas donne la préférence à la Confédération déclarant qu'il a une plus grande confiance dans les services suisses de sécurité ainsi que dans les dispositions que les autorités fédérales prendraient pour assurer à cette rencontre le secret nécessaire. Il "a encore insisté sur la nécessité qu'il y aurait à garder un secret rigoureux tant à l'égard des autorités françaises qu'à celui des autorités égyptiennes. Elles ne manqueraient pas, a-t-il dit, les unes et les autres, de 'torpiller' le projet si elles venaient à apprendre quelque chose.(73)" Il mentionne ainsi une des contraintes durables qui pèsent sur les entretiens franco-algériens : une partie des dirigeants arabes s'opposent à des pourparlers qui pourraient amener des concessions en faveur de la puissance coloniale. En juin 1959, F. Abbas déclare, lors d'une conférence de presse, que le gouvernement algérien est prêt à discuter avec des représentants français et il propose que ces pourparlers aient lieu en Suisse. Lui même séjourne à plusieurs reprises en Suisse dès 1956, y compris pour des raisons familiales puisque sa belle-mère, citoyenne française, vécut ses dernières années à Montreux. En août 1959, Feraht Abbas affirme à un inspecteur du MPF qu'il avait accepté de rencontrer le Premier Ministre français Michel Debré, mais que cette entrevue secrète mise sur pied par le journaliste René Payot n'avait pas pu se faire (74). En effet, celui-ci joue un rôle d’intermédiaire dans des pourparlers qui se heurtent au veto du général de Gaulle (75).

En juin 1960, les journaux évoquent la possibilité d'une rencontre du président français et de F. Abbas. Toutefois, Robert Kohli, secrétaire général du DPF de 1956 jusqu'à sa retraite fin juin 1961, estime peu vraisemblable que les Algériens demandent à la Suisse de jouer un rôle d'intermédiaire. A ses yeux, ils préféreront s'adresser à un pays qui aurait déjà reconnu le GPRA (76).

Au début du mois de juillet 1960, les journaux croient savoir que F. Abbas viendra en Suisse pour des entretiens avec des représentants français. En fait, l'échec de la conférence de Melun du 25 au 29 juin l'a fait renoncer à son projet de rencontrer le général de Gaulle (77).

En 1960, le DPF reste réservé dans ses relations avec les dirigeants algériens. Ainsi, quand le GPRA annonce qu'il a déposé auprès du gouvernement suisse les instruments portant adhésion aux quatre conventions de Genève pour la protection des victimes de guerre, le DPF tient à préciser que les documents lui ont été transmis par le Ministère libyen des affaires étrangères. Un communiqué est publié par le DPF le 21 juillet 1960 pour préciser que la réception de cette communication et sa notification aux autres gouvernements intéressés n'implique pas la reconnaissance par la Suisse du GPRA (78).

A la fin de 1960, des contacts se nouent avec Olivier Long, chef de la délégation suisse auprès de l’Association européenne de libre-échange. Bien qu'il n'ait pas une expérience particulière des problèmes algériens, il entretient des relations personnelles avec Louis Joxe et Michel Debré qui remontent à de nombreuses années et se fondent sur des liens familiaux (79).

Par l’intermédiaire de l'avocat Jean-Flavien Lalive, secrétaire général de la Commission internationale des juristes, Long est contacté par l’avocat genevois Raymond Nicolet (80). Celui-ci avait persuadé le délégué du FLN à Rome d’intervenir auprès des autorités guinéennes afin de libérer un Suisse détenu à Conakry. Nicolet fait ensuite des démarches à Berne pour que le représentant algérien puisse venir en Suisse. Il insiste sur son attitude pro-occidentale afin de surmonter les réticences des fonctionnaires fédéraux (81).
En effet, Boulharouf avait séjourné à Lausanne avant de s'installer à Rome(82). Son nom figure sur une liste de militants algériens interdits d’entrée en Suisse dès le 17 mai 1960. Le DFJP accepte d’accorder le 18 novembre un sauf-conduit pour un mois afin que Boulharouf puisse rencontrer son avocat. C'est ainsi qu'une première rencontre, le 23 décembre 1960, sera organisée avec Long qui, convaincu de la sincérité et du sérieux de son nouvel interlocuteur, transmet à ses amis parisiens la proposition algérienne. Avec l’accord du chef du DPF, Max Petitpierre informé dès le 16 décembre 1960, Long rencontre en secret à Paris le 10 janvier 1961 Louis Joxe, ministre d’État chargé des affaires algériennes.

C’est une combinaison fortuite qui aboutit à ces pourparlers qui n’ont pas été planifiés de longue date ni du côté des belligérants ni du côté suisse. La réussite est plus inopinée qu’anticipée. L'évolution générale du conflit qui menace de s'enliser dans une violence sans bornes, la maturation du processus qui rapproche les gouvernements français et algériens qui, l'un et l'autre pour des raisons différentes, estiment nécessaire de parvenir à un accord :
pour le GPRA, il s'agit de maintenir son autorité menacée par la montée en puissance des indépendantistes inspirés par le nassérisme ou le panarabisme et de parvenir à une coopération de l'Algérie indépendante avec la France. Pour le général de Gaulle, il est urgent de se débarrasser du boulet algérien pour consolider son régime et déployer sa politique étrangère dans le monde (83).

La démarche de Boulharouf ne résulte pas d’une décision précise du GPRA, mais s’insère parmi d’autres tentatives de rapprochements. D’emblée, ces contacts baignent dans un climat caractérisé par de multiples réticences et des méfiances réciproques. Afin de les surmonter, les bonnes volontés devront se manifester. Les blocages pourront être levés grâce aux interventions extérieures au conflit franco-algérien. C’est dans ce contexte que les diplomates suisses auront un rôle indispensable pour favoriser un climat de confiance qui permettent aux négociations d’avancer et d’aboutir à des accords.

En décembre 1960, le ministre français de la Justice, Edmond Michelet, propose que des entretiens soient organisés, ce qui est approuvé par le général de Gaulle. Du 1er au 5 janvier 1961, des entretiens secrets ont lieu à Genève entre l'ancien secrétaire d'Etat français Abdelkader Barakrok et son chef de cabinet et les deux envoyés algériens à Melun, Ahmed Boumendjel et Ahmed Francis (84). A son retour à Paris, le représentant français adresse une longue "note ultraconfidentielle" qui conclut à la possibilité et à la nécessité de reprendre les pourparlers "hors des frontières françaises".

En février 1961, une autre rencontre est organisée à Genève entre Claude Chayet, haut fonctionnaire du ministère français des AE, et Saad Dalhab, principal collaborateur de Belkacem Krim, chef de la diplomatie du GPRA (85).

Ces tentatives multiples sont organisées en secret, tendent à se concurrencer, voire à se court-circuiter dans un contexte de rumeurs les plus contradictoires et de passions les plus violentes.

Le 18 février 1961, de Gaulle adresse une note à Georges Pompidou (86) et Bruno de Leusse (87) pour leur préciser les buts et les limites de leur mission d’information (88). Les deux émissaires français discutent le 20 février avec Boulharouf et Ahmed Boumendjel, directeur politique du Ministère de l’Information du GPRA. Le 5 mars, une deuxième rencontre secrète se déroule à Neuchâtel avec les mêmes protagonistes. Les responsables suisses, O. Long et Gianrico Bucher, chef de la section Est du DPF, se chargent de la sécurité et du secret des entretiens sans participer aux séances. Lors des conversations avec les différents protagonistes, ils formulent des propositions pour surmonter les obstacles, dissiper les méfiances et ouvrir la possibilité de négociations publiques.

Par un télégramme secret du 20 mars 1961, le DPF demande à l'Ambassade de Suisse à Tunis d'adopter une attitude compréhensive vis-à-vis des membres du GPRA et de renoncer à exiger des renseignements précis sur les motifs et les dates des voyages des personnes dont le GPRA prend la responsabilité.