The Earth’s transition zone, at depths of 410–660 km, while being composed of nominally anhydrous magnesium silicate minerals, may be subject to significant hydration. Little is known about the mechanism of hydration, despite the vital role this plays in the physical and chemical properties of the mantle, leading to a need for improved structural characterization. Here we present an ab initio random structure searching (AIRSS) investigation of semihydrous (1.65 wt % H₂O) and fully hydrous (3.3 wt % H₂O) wadsleyite. Following the AIRSS process, k-means clustering was used to select sets of structures with duplicates removed, which were then subjected to further geometry optimization with tighter constraints prior to NMR calculations. Semihydrous models identify a ground-state structure (Mg3 vacancies, O1–H hydroxyls) that aligns with a number of previous experimental observations. However, predicted NMR parameters fail to reproduce low-intensity signals observed in solid-state NMR spectra. In contrast, the fully hydrous models produced by AIRSS, which enable both isolated and clustered defects, are able to explain observed NMR signals via just four low-enthalpy structures: (i) a ground state, with isolated Mg3 vacancies and O1–H hydroxyls; (ii/iii) edge-sharing Mg3 vacancies with O1–H and O3–H species; and (iv) edge-sharing Mg1 and Mg3 vacancies with O1–H, O3–H, and O4–H hydroxyls. Thus, the combination of advanced structure searching approaches and solid-state NMR spectroscopy is able to provide new and detailed insight into the structure of this important mantle mineral.