Bien que l’Algérie affirme ne pas être une partie prenante dans le conflit du Sahara occidental, dans les années 2000, le voisin de l’Est avait fait une proposition suggérant de diviser le territoire entre le Maroc et le Front Polisario. Alger avait aussi par le passé proposé à ce que l’ONU administre elle-même le Sahara.
Fin des années 90, les Nations unies arrivent à la conclusion selon laquelle une mise en œuvre du plan de règlement du Sahara occidental, basé sur un référendum, conduira à deux choix : l’intégration du territoire au Maroc ou son indépendance. Mais l’ONU fera vite face à l’impasse, en raison des profondes divergences entre le Front Polisario et l’Algérie d’une part, et le Maroc d’autre part, concernant les personnes qui ont le droit de voter.
En juin 2000, le Conseil de sécurité des Nations unies adopte une proposition de James Baker, alors envoyée spécial de l’ONU pour le Sahara occidental. Un accord-cadre qui évoque l’exercice, par les Sahraouis, du pouvoir dans la province, par l’intermédiaire d’organes exécutifs, législatifs et judiciaires. Selon le plan Baker, le Maroc garde l’autorité totale sur les relations extérieures. Cinq ans plus tard, le statut du Sahara devait alors faire l’objet d’un référendum à une date convenue par les deux parties. Seulement, pour qu’un électeur ait le droit de voter à ce référendum, il doit avoir résidé de manière permanente dans le Sahara tout au long de l’année précédant le référendum.
Le Maroc était le premier à réagir à cette initiative. «Au début de 2001, mon Envoyé personnel a été en mesure de décider que le Maroc, puissance administrant le Sahara occidental, était prêt à appuyer un projet d’accord», indique alors le Secrétaire général de l’ONU dans un rapport sur la situation concernant le Sahara occidental, publié le 23 mai 2003. «Cet accord prévoit le transfert du pouvoir aux habitants du territoire alors que le statut définitif du territoire doit être décidé par référendum, cinq ans plus tard», indique Kofi Annan, alors secrétaire général de l’ONU.