The reversible intercalation of multivalent cations, especially Mg2+, into a solid-state electrode is an attractive mechanism for next-generation energy storage devices. These reactions typically exhibit poor kinetics due to a high activation energy for interfacial charge-transfer and slow solid-state diffusion. Interlayer water in V2O5 and MnO2 has been shown to improve Mg2+ intercalation kinetics in nonaqueous electrolytes. Here, the effect of structural water on Mg2+ intercalation in nonaqueous electrolytes is examined in crystalline WO3 and the related hydrated and layered WO3·nH2O (n = 1, 2). Using thin film electrodes, cyclic voltammetry, Raman spectroscopy, X-ray diffraction, and electron microscopy, the energy storage in these materials is determined to involve reversible Mg2+ intercalation. It is found that the anhydrous WO3 can intercalate up to ∼0.3 Mg2+ (75 mAh g-1) and can maintain the monoclinic structure for at least 50 cycles at a cyclic voltammetry sweep rate of 0.1 mV s-1. The kinetics of Mg2+ storage in WO3 are limited by solid-state diffusion, which is similar to its behavior in a Li+ electrolyte. On the other hand, the maximum capacity for Mg2+ storage in WO3·nH2O is approximately half that of WO3 (35 mAh g-1). However, the kinetics of both Mg2+ and Li+ storage in WO3·nH2O are primarily limited by the interface and are thus pseudocapacitive. The stability of the structural water in WO3·nH2O varies: the interlayer water of WO3·2H2O is removed upon exposure to a nonaqueous electrolyte, while the water directly coordinated to W is stable during electrochemical cycling. These results demonstrate that tungsten oxides are potential candidates for Mg2+ cathodes, that in these materials structural water can lead to improved Mg2+ kinetics at the expense of capacity, and that the type of structural water affects stability.