Trong suốt lịch sử, Gao đã là một điểm đến và dừng chân trên tuyến đường [[giao thương Liên Sahara]]. Vào thế kỷ IX, những cây viết người Ả Rập đã mô tả Gao là một đô thị quan trọng trong khu vực<ref>{{cite book|last1=Levtzion|first1=Nehemia|title=Ancient Ghana and Mali|date=1973|publisher=Methuen & Co Ltd|location=New York|isbn=0-8419-0431-6|page=3}}</ref>
và đến cuối thế kỷ XX, lãnh đạo địa phương đã cải giáo sang Hồi giáo. Đến thế XIII, Gao sáp nhập vào [[Đế quốc Mali]], đến thế kỷ XV thì lấy lại độc lập, nhưng sau cuộc xâm lược của [[Sonni Ali]] (trị vì 1464–1492) nó trở thành thủ đô [[Đế quốc Songhai]]. Đế quốc Songhai sụp đổ năm 1591 do những cuộc càng quét của Maroc; [[Timbuktu]] đóng vai trò thủ đô mới. Đến lúc nhà thám hiểm [[Heinrich Barth]] đặt chân đến đây năm 1854, Gao đã sụt xuống thành một ngôi làng xơ xác với 300 túp lều.
Ngày 31 tháng 3, năm 2012, Gao bị chiếm giữ bởi lực lượng [[Phong trào Dân tộc Giải phóng Azaward]] (MNLA) và phiến quân [[Ansar Dine]]. Sau khi chiếm thêm [[Kidal]] và [[Timbuktu]], ngày 6 tháng 4, MNLA tuyên bố toàn vùng độc lập khỏi Mali với tên gọi [[Azawad]]<ref name="english.alarabiya.net">{{cite news|url=http://english.alarabiya.net/articles/2012/04/06/205763.html|publisher=Al Arabiya|title=Tuareg rebels declare the independence of Azawad, north of Mali|date=6 April 2012|accessdate=6 April 2012}}</ref> và chọn Gao làm thủ đô.<ref>{{cite news|url=http://www.aljazeera.com/news/africa/2012/04/20124644412359539.html|publisher=Al Jazeera|date=6 April 2012|accessdate=6 April 2012|title=Tuaregs claim 'independence' from Mali}}</ref> MNLA mất quyền kiểm soát vào tay dân quân Hồi giáo trong [[trận Gao]] ngày 26-27 tháng 6, năm 2012. Ngày 26 tháng 1, năm 2013, thành phố được quân lực Pháp và Mali tái chiếm trong [[Opération Serval]].<ref>{{citation |title=Mali: French-led soldiers 'in control of Gao' |url=https://www.bbc.co.uk/news/world-africa-21210496 | publisher=BBC News | date=26 January 2013 | accessdate=26 January 2013}}.</ref>
