Looming concerns regarding scarcity, high prices and safety threatens the long-term use of lithium in energy storage devices. Calcium has been explored in batteries because of its abundance and low-cost, but the larger size and higher charge density of calcium-ions relative to lithium impairs diffusion kinetics and cyclic stability. In this work, an aqueous calcium-ion battery is demonstrated using orthorhombic, trigonal and tetragonal polymorphs of molybdenum vanadium oxide (MoVO) as a host for calcium ions. Orthorhombic and trigonal MoVO outperforms the tetragonal structure because large hexagonal and heptagonal tunnels are ubiquitous in such crystals, providing facile pathways for calcium diffusion. For trigonal MoVO, a specific capacity of ~203 mAh g-1 was obtained at ~0.2C and at 100 times faster rate of ~20C, ~60 mAh g-1 capacity was achieved. The open-tunnel trigonal and orthorhombic polymorphs also promote cyclic stability and reversibility, showing a capacity fade rate of ~0.15% per cycle. A review of the literature indicates that MoVO provides one of the best performances reported to date for the storage of calcium.