We investigate the perchlorate anion, ClO4-, microhydrated with up to eight water molecules using infrared photodissociation (IRPD) spectroscopy aided by density functional theory computations. The features observed in the IRPD spectra of D2-tagged ClO4-(H2O)n with n = 0-8 in the O-H stretching (2800-3800 cm-1) and fingerprint (800-1800 cm-1) spectral ranges are assigned to vibrational modes of the solvent, i.e., free and hydrogen-bonded O-H stretching and H2O bending modes, and of the solute, i.e., perchlorate stretching modes. The splitting of the triply degenerate antisymmetric stretching mode in the bare ClO4- (1102 cm-1) upon microhydration directly reports on the symmetry of the local solvation network, while the red-shift of the hydrogen-bonded O-H stretching bands in comparison to those of free O-H oscillators (>3700 cm-1) reflects the strength of the anion-water (3550-3650 cm-1) and water-water (3240-3540 cm-1) hydrogen bonds. The stronger water-water interaction leads to an early onset of water-water hydrogen bond formation (n = 2) and eventually asymmetric solvation of ClO4-, evidenced by the population of the second and third hydration shells at n = 5 and n = 8, respectively, before the first hydration shell is completed. The present study provides a bottom-up view of the initial stages of hydrogen-bond network formation around a high surface propensity anion, and these insights are discussed in the context of recent results obtained for the water-vapor interface of perchlorate solutions.