String theory suggests the simultaneous presence of many ultralight axions possibly populating each decade of mass down to the Hubble scale 10^-33eV. Conversely the presence of such a plenitude of axions (an "axiverse") would be evidence for string theory, since it arises due to the topological complexity of the extra-dimensional manifold and is ad hoc in a theory with just the four familiar dimensions. We investigate how upcoming astrophysical experiments will explore the existence of such axions over a vast mass range from 10^-33eV to 10^-10eV. Axions with masses between 10^-33eV to 10^-28eV cause a rotation of the CMB polarization that is constant throughout the sky. The predicted rotation angle is of order α~1/137. Axions in the mass range 10^-28eV to 10^-18eV give rise to multiple steps in the matter power spectrum, that will be probed by upcoming galaxy surveys. Axions in the mass range 10^-22eV to 10^-10eV affect the dynamics and gravitational wave emission of rapidly rotating astrophysical black holes through the Penrose superradiance process. When the axion Compton wavelength is of order of the black hole size, the axions develop "superradiant" atomic bound states around the black hole "nucleus". Their occupation number grows exponentially by extracting rotational energy from the ergosphere, culminating in a rotating Bose-Einstein axion condensate emitting gravitational waves. This mechanism creates mass gaps in the spectrum of rapidly rotating black holes that diagnose the presence of axions. The rapidly rotating black hole in the X-ray binary LMC X-1 implies an upper limit on the decay constant of the QCD axion f_a<2*10^17GeV, much below the Planck mass. This reach can be improved down to the grand unification scale f_a<2*10^16GeV, by observing smaller stellar mass black holes.

42 pages, 10 figures;v2: refs and minor changes added