In order to fulfil the future requirements of electrochemical energy storage, such as high energy density at high power demands, heterogeneous nanostructured materials are currently studied as promising electrode materials due to their synergic properties, which arise from integrating multi-nanocomponents, each tailored to address a different demand (e. g., high energy density, high conductivity, and excellent mechanical stability). In this article, we discuss these heterogeneous nanomaterials based on their structural complexity: zero-dimensional (0-D) (e. g. core-shell nanoparticles), one-dimensional (1-D) (e. g. coaxial nanowires), two-dimensional (2-D) (e. g. graphene based composites), three-dimensional (3-D) (e. g. mesoporous carbon based composites) and the even more complex hierarchical 3-D nanostructured networks. This review tends to focus more on ordered arrays of 1-D heterogeneous nanomaterials due to their unique merits. Examples of different types of structures are listed and their advantages and disadvantages are compared. Finally a future 3-D heterogeneous nanostructure is proposed, which may set a goal toward developing ideal nano-architectured electrodes for future electrochemical energy storage devices.