For magnesium ion batteries (MIBs) to be used commercially, new cathodes must be developed that show stable reversible Mg intercalation. VS4 is one such promising material, with vanadium and disulfide anions [S2]2- forming one-dimensional linear chains, with a large interchain spacing (5.83 Å) enabling reversible Mg insertion. However, little is known about the details of the redox processes and structural transformations that occur upon Mg intercalation and deintercalation. Here, employing a suite of local structure characterization methods including X-ray photoelectron spectroscopy (XPS), V and S X-ray absorption near-edge spectroscopy (XANES), and 51V Hahn echo and magic-angle turning with phase-adjusted sideband separation (MATPASS) NMR, we show that the reaction proceeds via internal electron transfer from V4+ to [S2]2-, resulting in the simultaneous and coupled oxidation of V4+ to V5+ and reduction of [S2]2- to S2-. We report the formation of a previously unknown intermediate in the Mg-V-S compositional space, Mg3V2S8, comprising [VS4]3- tetrahedral units, identified by using density functional theory coupled with an evolutionary structure-predicting algorithm. The structure is verified experimentally via X-ray pair distribution function analysis. The voltage associated with the competing conversion reaction to form MgS plus V metal directly is similar to that of intermediate formation, resulting in two competing reaction pathways. Partial reversibility is seen to re-form the V5+ and S2- containing intermediate on charging instead of VS4. This work showcases the possibility of developing a family of transition metal polychalcogenides functioning via coupled cationic-anionic redox processes as a potential way of achieving higher capacities for MIBs.