The development of advanced energy storage devices is at the forefront of research geared towards a sustainable future. Nanostructured materials are advantageous in offering huge surface to volume ratios, favorable transport features, and attractive physicochemical properties. They have been extensively explored in various fields of energy storage and conversion. This review is focused largely on the recent progress in nanostructured Mo-based electrode materials including molybdenum oxides (MoO(x), 2 ≤ x ≤ 3), dichalconides (MoX2, X = S, Se), and oxysalts for rechargeable lithium/sodium-ion batteries, Mg batteries, and supercapacitors. Mo-based compounds including MoO2, MoO3, MoO(3-y) (0 < y < 1), MMo(x)O(y) (M = Fe, Co, Ni, Ca, Mn, Zn, Mg, or Cd; x = 1, y = 4; x = 3, y = 8), MoS2, MoSe2, (MoO2)2P2O7, LiMoO2, Li2MoO3, etc. possess multiple valence states and exhibit rich chemistry. They are very attractive candidates for efficient electrochemical energy storage systems because of their unique physicochemical properties, such as conductivity, mechanical and thermal stability, and cyclability. In this review, we aim to provide a systematic summary of the synthesis, modification, and electrochemical performance of nanostructured Mo-based compounds, as well as their energy storage applications in lithium/sodium-ion batteries, Mg batteries, and pseudocapacitors. The relationship between nanoarchitectures and electrochemical performances as well as the related charge-storage mechanism is discussed. Moreover, remarks on the challenges and perspectives of Mo-containing compounds for further development in electrochemical energy storage applications are proposed. This review sheds light on the sustainable development of advanced rechargeable batteries and supercapacitors with nanostructured Mo-based electrode materials.