La fin des années 50
représente un tournant dans l'histoire de la région
avec la maturation des mouvements d'indépendance africains et
arabes. L'Espagne qui est en train de consolider sa présence,
notamment avec le début de l'exploitation économique,
se trouve ainsi confrontée à un double problème:
la reprise de la lutte du peuple sahraoui et les revendications
étrangères.Le 2 mars 1956 le Maroc accède à l'indépendance. Sous l'impulsion du parti de l'Istiqlal, qui a élaboré un an auparavant une carte du "Grand Maroc" allant de la Méditerranée jusqu'au fleuve Sénégal en passant par une partie de l'Algérie, le Maroc commence à réclamer officiellement les territoires sous occupation espagnole et française. Continuant le combat entrepris au sein de l'Armée de Libération Marocaine, les Sahraouis effectuent une série d'attaques jusqu'en Mauritanie. Cette continuation de la lutte armée pour libérer la région met en difficulté l'Espagne. Le Maroc retire alors son appui, mais il faut une opération combinée des armées françaises et espagnoles, pour rétablir l'ordre au Sahara: c'est l'opération "Ecouvillon" de février 1958.
Un décret espagnol du 10 janvier de la même année établit deux provinces séparées: Ifni et le Sahara Occidental. La zone de Tarfaya est "rétrocédée" au Maroc. Administré comme une province métropolitaine, le Sahara est représenté aux Cortès, le parlement espagnol, par trois députés. Le pouvoir est attribué à un gouverneur général dépendant du président du gouvernement, le général Franco. Des élections établies sur une base assez réduite et corporatiste, désignent des conseils provinciaux.
La décision de la France de créer la République Islamique de Mauritanie, le 28 novembre 1958, réanime les ambitions marocaines. La proclamation de son indépendance, le 28 novembre 1960, déclenche une longue querelle entre le Maroc et la Mauritanie qui, à son tour, commence à revendiquer des droits sur le Sahara. Les ambitions marocaines n'épargnent pas l'Algérie engagée dans sa lutte de libération. Après l'indépendance le gouvernement algérien est immédiatement confronté au problème et l'intransigeance marocaine conduit à l'affrontement armé d'octobre 1963.
Les revendications marocaines maintiennent une tension jusqu'en 1970. Après un règlement bilatéral avec l'Algérie puis avec la Mauritanie la rencontre de Nouadhibou, le 14 septembre, permet d'arriver, entre autres, à un accord commun sur la question du Sahara. Chacun admet le principe de l'autodétermination sur la base de la résolution de l'Assemblée générale de l'O.N.U du 16 décembre 1965. Le Maroc semble donc abandonner ses prétentions, un accord avec l'Espagne lui ayant permis d'obtenir en 1969 l'enclave d'Ifni. En échange, l'Espagne maintient sa présence à Ceuta, Melilla et aux îles Jafarines
La question du Sahara, entre temps, est portée à l'attention des instances internationales, et notamment des Nations Unies. L'Espagne, elle, prépare l'exploitation des mines de phosphates de Bou Craa.
Le 16 octobre 1964 le comité de décolonisation de l'O.N.U. adopte une résolution demandant à l'Espagne d'appliquer pour Ifni et le Sahara Occidental, la résolution du 14 décembre 1960 sur l'octroi de l'indépendance aux pays sous domination coloniale. Mais aucune mention n'est faite des revendications du Maroc et de la Mauritanie, ce qui n'engage pas Madrid à traiter avec ces pays. L'année suivante, le 16 décembre, l'Assemblée Générale adopte une résolution qui demande à l'Espagne de prendre des mesures en vue de décoloniser les deux territoires.
Le 20 décembre 1966, l'Assemblée générale de l'O.N.U. approuve une nouvelle résolution invitant l'Espagne à organiser un référendum, sous le contrôle des Nations Unies, de manière à permettre à la population autochtone de s'exprimer librement, et de prévoir le retour des exilés.
Cette même année l'Algérie est appelée à discuter de la question devant le comité de décolonisation de l'O.N.U. en tant que partie intéressée. Elle souligne qu'elle n'a pas de revendications territoriales mais que seule la préoccupe la décolonisation d'un pays limitrophe qui fait l'objet, comme une partie de son territoire d'ailleurs, des convoitises d'un autre pays voisin.