Magnesium batteries have received attention as a type of post-lithium-ion battery because of their potential advantages in cost and capacity. Among the host candidates for magnesium batteries, orthorhombic α-V2O5 is one of the most studied materials, and it shows a reversible magnesium intercalation with a high capacity especially in a wet organic electrolyte. Studies by several groups during the last two decades have demonstrated that water plays some important roles in getting higher capacity. Very recently, proton intercalation was evidenced mainly using nuclear resonance spectroscopy. Nonetheless, the chemical species inserted into the host structure during the reduction reaction are still unclear (i.e., Mg(H2O)n2+, Mg(solvent, H2O)n2+, H+, H3O+, H2O, or any combination of these). To characterize the intercalated phase, the crystal structure of the magnesium-inserted phase of α-V2O5, electrochemically reduced in 0.5 M Mg(ClO4)2 + 2.0 M H2O in acetonitrile, was solved for the first time by the ab initio method using powder synchrotron X-ray diffraction data. The structure was tripled along the b-axis from that of the pristine V2O5 structure. No appreciable densities of elements were observed other than vanadium and oxygen atoms in the electron density maps, suggesting that the inserted species have very low occupancies in the three large cavity sites of the structure. Examination of the interatomic distances around the cavity sites suggested that H2O, H3O+, or solvated magnesium ions are too big for the cavities, leading us to confirm that the intercalated species are single Mg2+ ions or protons. The general formula of magnesium-inserted V2O5 is Mg0.17HxV2O5, (0.66 ≤ x ≤ 1.16). Finally, density functional theory calculations were carried out to locate the most plausible atomic sites of the magnesium and protons, enabling us to complete the structure modeling. This work provides an explicit answer to the question about Mg intercalation into α-V2O5.