Polisario ble grunnlagt i 1973, da Spania fortsatt var kolonimakt i Spansk Sahara (senere Vest-Sahara). 20. mai samme år gjennomførte Polisario det første væpnede angrepet mot spanske styrker. Til tross for at de bare var bevæpnet med gamle håndvåpen, kom de overraskende på soldatene ved den spanske posteringen Khanga, og vant en viktig symbolsk seier.
Polisarios væpnede kamp ga Spania store problemer med å beholde kontrollen, og de ble snart nødt til å trekke seg tilbake fra innlandet. Sommeren 1975 hadde Spania bare kontroll over byene Dachla, l’Ayoune og Smara. En av årsaken til Spanias manglende kontroll var at regimet til Franco var i ferd med å gå i oppløsning, og landet hadde verken kapasitet eller politisk kraft til å føre kolonikrig.
Den 26. februar 1976 trakk Spania seg offisielt ut av området, og overlot formelt administrasjonen til Marokko og Mauritania gjennom den såkalte Madridavtalen. Polisario var ikke interessert i å la spanierne etterlate noe politisk vakuum, og utropte dagen etter en egen republikk – Den sahrawiske arabiske demokratiske republikk – i Bir Lehlou, som ligger i det nordøstlige Vest-Sahara.
I de påfølgende år kom det til harde kamper mellom Polisario og den marokkanske hæren. Marokko greide ikke å få kontroll over ørkenen i den østlige delen av Vest-Sahara. Polisario opererte fra baser i Algerie og angrep marokkanske konvoier og utposter gjennom geriljaangrep. Marokko endret taktikk, forlot garnisonene og utpostene i de fjerntliggende delene av Vest-Sahara, og forsterket isteden befestningen rundt byene.
Polisario fortsatte sine angrep, og gjorde livet stadig vanskeligere for den marokkanske hæren. Marokko skiftet derfor igjen taktikk, og delte landet i to på langs, med en mur og høye voller av sand og stein. På vollene ble det bygget festningsverk, og det ble lagt brede minefelt på hver side. Murens beliggenhet og utstrekning skifet med Polisarios angrep og Marokkos motangrep, men ved våpenhvilen som ble inngått i 1991 var muren 2 400 kilometer lang, og gikk fra nord til syd gjennom hele landet. Marokko har siden det hatt kontroll over to tredjeler i vest, mens Polisario har kontroll over den resterende tredjedel i øst.