Vuodesta 1612 lähtien Gaoa hallitsivat ''[[armat|arma]]''-nimellä tunnetut marokkolaissotilaiden sekarotuiset jälkeläiset. Tuaregit valloittivat sen ensimmäisen kerran vuonna 1680 ja uudelleen vuonna 1770. 1800-luvun puolivälissä kaupunki oli taantunut muutaman sadan talon kyläksi. [[Ranska]]laiset [[siirtomaa]]isännät perustivat sinne varuskunnan vuonna 1899.<ref name="islam" />
[[Tuaregikapina (2012)|Vuoden 2012 tuaregikapinan]] aikana [[Azawadin kansallinen vapautusliike|Azawadin kansallisen vapautusliikkeen]] MNLA:n joukotvaltasivatvaltasi Gaon hallituksen joukoilta. Myöhemmin MNLA julisti Pohjois-Malin [[Azawad]]in alueen itsenäiseksi ja valitsi Gaon sen pääkaupungiksi.<ref name="aljazeera">{{Verkkoviite | Osoite= http://www.aljazeera.com/news/africa/2012/04/20124644412359539.html | Nimeke= Tuaregs claim 'independence' from Mali | Julkaisija= Aljazeera | Ajankohta= 6.4.2012 | Viitattu= 5.3.2013 | Kieli= {{en}} }}</ref> [[Islamismi|Islamistit]] valtasivat kaupungin tuaregeilta kesäkuussa 2012<ref>{{Verkkoviite | Osoite = http://www.bbc.com/news/world-africa-18610618 | Nimeke = BBC News – Mali: Islamists seize Gao from Tuareg rebels | Tekijä = | Ajankohta = | Julkaisija = | Viitattu = 16.9.2014 | Kieli= {{en}} }}</ref>. Ranskalaisten tukema Malin armeija sai Gaon uudelleen hallintaansa tammikuussa 2013<ref>{{Verkkoviite | Osoite = http://uk.reuters.com/article/2013/01/26/uk-mali-rebels-idUKBRE90P0A120130126?feedType=RSS&feedName=worldNews | Nimeke = Reuters: French, Malian forces capture Gao rebel stronghold | Tekijä = | Ajankohta = | Julkaisija = | Viitattu = 16.9.2014 | Kieli= {{en}} }}</ref>.
