Self-assembly via nanoscale phase-separation offers an elegant route to fabricate nanocomposites with physical properties unattainable in single-component systems. One important class of nanocomposites are optical metamaterials which exhibit exotic properties and lead to opportunities for agile control of light propagation. Such metamaterials are typically fabricated via expensive and hard-to-scale top-down processes requiring precise integration of dissimilar materials. In turn, there is a need for alternative, more efficient routes to fabricate large-scale metamaterials for practical applications with deep-subwavelength resolution. Here, we demonstrate a bottom-up approach to fabricate scalable nanostructured metamaterials via spinodal decomposition. To demonstrate the potential of such an approach, we leverage the innate spinodal decomposition of the VO2-TiO2 system, the metal-to-insulator transition in VO2, and thin-film epitaxy, to produce self-organized nanostructures with coherent interfaces and a structural unit cell down to 15 nm (tunable between horizontally- and vertically-aligned lamellae) wherein the iso-frequency surface is temperature-tunable from elliptic- to hyperbolic-dispersion producing metamaterial behavior. These results provide an efficient route for the fabrication of nanostructured metamaterials and other nanocomposites for desired functionalities.