La presència del primer assentament permanent en el que avui és la ciutat d'Al-Aaiun data de 1928, quan es va establir un lloc de vigilància pertanyent a la tribu izarguien. Els espanyols no van començar l'ocupació efectiva de l'interior del territori fins a 1934, quan el comandant Antonio de Oro Pulido i el capità Galo Bullón Díaz van arribar fins al lloc de vigilància dels izarguien, trobant òptim el lloc per a un establiment permanent, car no estava lluny del mar i sí ben comunicat amb Tarfaya i Cap Juby, i comptava amb un subministrament garantit d'aigua dolça gràcies als pous de la riba esquerra del Saguia el Hamra, així com el seu embassament al seu llit durant l'època de pluges. Quatre anys després, en 1938, tots dos oficials van decidir l'establiment d'un lloc militar fix, i es van erigir llavors els primers edificis permanents de l'assentament. En 1940 va ser designada oficialment ciutat capital o capçalera del Sàhara Espanyol, rebent per tant una dotació de Partides Específiques (per a la construcció d'edificis i infraestructures) pertanyent als Pressupostos Anuals independents per a la regió Ifni-Sàhara. El seu desenvolupament va ser lent fins als anys seixanta, quan va tenir un desenvolupament espectacular convertint-se en una ciutat moderna.[1]

El 17 de juny de 1970 un grup de manifestants encapçalats per Mohammed Bassiri van portar una petició al governador general del Sàhara Espanyol a Al Aaiun.[2] El fet, conegut com a revolta de Zemla, acabà amb la policia dispersant la manifestació i arrestant els capitostos, i arran la resistència la Legió Espanyola va disparar contra la multitud, provocant onze morts. Centenars foren detinguts, entre ells Bassiri, que fou assassinat a la presó.[2]

Va ser la capital de l'antic Sàhara Espanyol fins a desembre de 1975, quan després de la marxa pacífica de milers de marroquines cap al Sahara –planificada pel rei Hassan II– que després es va denominar "marxa verda", es van signar els Acords de Madrid, pels quals Espanya va cedir el Sàhara al Marroc i a Mauritània, els quals van haver d'enfrontar-se després amb el saharaui Front Polisario, recolzat per Algèria. Els marroquins van ocupar la ciutat a principis de 1976, causant un èxode de saharauis cap a Algèria per escapar de les represàlies marroquines pel seu suport al Front Polisario. En la seva persecució a la població que fugia cap al sud-oest de Algèria, les forces aèries marroquines van utilitzar napalm, fòsfor blanc i bombes de fragmentació contra els refugiats.

En 2005, la ciutat va ser escenari de greus protestes en contra de l'ocupació marroquina i en suport de la independència i del Front Polisario. Aquestes protestes també es van produir en altres nuclis urbans del Sahara Occidental, així com en alguns centres universitaris de tot el Marroc. La ciutat ha estat reconeguda com la capital de la República Àrab Sahrauí Democràtica per 81 estats.