Tuaregit perustivat Agadezin 1000-luvulla. Agadezista tuli 1400-luvulla Aïrin sulttaanikunnan pääkaupunki, ja se oli 1500-luvulle asti merkittävä kaupankäyntikeskus. Kaupunki kuului Songhain kuningaskuntaan 1500-luvulla, jolloin Agadez kukoisti ja sai uusia asukkaita kauppiaista ja käsityöläisistä. Songhain kuningaskunta hajosi vuonna 1591. Seuraavien vuosisatojen kuluessa Agadez kärsi muun muassa tuaregilevottomuuksista, epidemioista ja kuivuudesta. Kaupunki menetti kaupallisen merkityksensä 1700-luvun lopussa, ja seuraavan vuosisadan puoliväliin mennessä osa Agadezista, muun muassa kuuluisa moskeija, oli raunioina. Ranskalaiset valloittivat Agadezin muiden Nigerin pohjoisosien mukana 1900-luvun alussa, ja kaupunki oli Nigerin itsenäistymiseen eli vuoteen 1960 saakka Ranskan sotilashallinnon alaisena. Tuaregit ovat kapinoineet Agadezista käsin Nigerin hallitusta vastaan aiemmin 1990-luvun alussa ja uudelleen vuosina 2007–2009 Agadezin historiallinen keskusta liitettiin Unesconmaailmanperintöluetteloon vuonna 2013.