Large-scale stationary storage forms a key sector that can be economically served by sodium-ion batteries. In realizing practical sodium-ion batteries, discovery and development of novel cathodes is essential. In this spirit, alluaudite-type Na2Fe2(SO4)3 was reported in 2014 to have the highest Fe3+/Fe2+ redox potential (~3.8 V vs. Na). This finding led to reports on various PO43- and SO42- based alluaudite compounds exhibiting high energy densities. In 2017, MoO42- based alluaudite, Na2.67Mn1.67(MoO4)3, was found as a 3.45 V cathode material. Exploring molybdenum chemistry further, this work reports alluaudite type Na3.36Co1.32(MoO4)3 (NCMo) as a novel versatile electroactive cathode for Li-ion and Na-ion batteries. It was synthesized by a wet solution-combustion route with a restricted annealing duration of 1 min at 600 °C. Calorimetric study revealed the formation enthalpy from component oxides (ΔH°f,ox = -575.49 ± 7.75 kJ/mol) to be highly exothermic. Unlike the sulfate class of alluaudites, this material is highly stable in air and moisture (ΔHds = 537.42 ± 0.78 kJ/mol). Having an ionic conductivity of 6.065 × 10-8 S/cm (at 50 °C), it offers a pseudo two-dimensional Naþ migration pathway. Without any material optimization, NCMo was found to work as a high-voltage insertion cathode (ca. 4.0 V vs. Na/Na+ and 4.1 V vs. Li/Li+) in sync with theoretically predicted potential of 3.98 V (vs. Na/Na+). Ex-situ X-ray diffraction and photoelectron spectroscopy studies revealed the occurrence of solid-solution redox mechanism solely involving Co3+/Co2+ redox centre. It benchmarks Na3.36Co1.32(MoO4)3 as a novel electrochemically active Mo-based alluaudite-type polyanionic cathode insertion material.