Un petit groupe d'environ vingt-cinq sahraouis, parmi lesquels un jeune Reguibi nommé Abba el-Cheikh, rejoignit l'Armée de libération dans le Sud marocain en 1956 et fut ensuite envoyé dans le désert pour inciter les nomades à la révolte. Leur argument était que si l'on avait réussi à forcer la France et l'Espagne à accorder au Maroc l'indépendance, a fortiori, on pourrait certainement les chasser du Sahara qu'elles n'avaient assujetti que vingt ans auparavant.

De nombreux Sahraouis furent convaincus qu'ils pourraient regagner leurs libertés d'antan en revenant à leurs traditions guerrières, et ainsi, plusieurs djemaas, notamment celles des tribus zekna et des Reguibat, résolurent de suivre l'exemple de l'Armée de libération. Ils commencèrent par former des unités de guérilleros composées exclusivement de Sahraouis qui, bien qu'utilisant certains armements modernes fournis par l'Armée de libération, calquèrent leurs tactiques sur les techniques du ghazi qu'ils pratiquaient jadis.

Pendant ce temps, l'Armée de libération avait commencé à attaquer au Sahara occidental. Le 29 novembre, des guérilleros arrivèrent au phare du Cap Bojador qui n'était pratiquement pas défendu, capturèrent les 7 Espagnols qui s'y trouvaient et sabotèrent le phare, le mettant hors d'usage pour plusieurs jours.

Le 3 décembre, le ministère des Armées annonçait à Madrid que les guérilleros avaient attaqué un convoi espagnol à Arbaa el Mesti, près d'El-Aïoun. Il y eut un autre affrontement à 20 kilomètres d'El. Aïoun le 22 décembre, et, le 3 janvier 1958, l'Armée de libération attaqua les positions espagnoles à Argoub situé face à Villa Cisneros, de l'autre côté de la baie du Rio de Oro.