Vanadium oxide double-preintercalated with Al3+ and poly(3,4-ethylenedioxythiophene) (Al0.18V2O5/PEDOT) was synthesized using a two-step hydrothermal method. The presence of Al3+ ions in the layered structure of Al0.18V2O5 and PEDOT in the double-preintercalated material was confirmed. The electrochemical performance of Al0.18V2O5/PEDOT cathodes in Mg2+-containing acetonitrile electrolyte was investigated by cyclic voltammetry and galvanostatic charge–discharge. The large interlayer distance of 14.02 Å allows Al0.18V2O5/PEDOT to reversibly intercalate magnesium ions into its crystal lattice. The cathodes achieved a high reversible capacity of 138 mAh·g−1 at a low current density (0.02 A·g−1) and demonstrated superior cycling performance, retaining 95.5% of capacity after 500 cycles at 0.1 A·g−1. This confirms that the dual modification approach is efficient for obtaining advanced magnesium-ion battery cathodes.