A central feature of materials synthesis is the concept of phase diagrams, which provide information on the phases of the material at any given thermodynamic condition (i.e., state variables such as pressure, temperature and composition). Conventional phase diagram generation involves experimentation to provide an initial estimate of the set of thermodynamically accessible phases and their boundaries, followed by use of phenomenological models to interpolate between the available experimental data points and extrapolate to experimentally inaccessible regions. Such an approach, combined with high throughput first-principles calculations and data-mining techniques, has led to exhaustive thermodynamic databases (e.g. compatible with the CALPHAD method), albeit focused on the reduced set of phases observed at distinct thermodynamic equilibria. In contrast, materials during their synthesis, operation, or processing, may not reach their thermodynamic equilibrium state but, instead, remain trapped in a local (metastable) free energy minimum, which may exhibit desirable properties. A phase diagram that maps these metastable phases and their thermodynamic behavior is highly desirable but currently lacking, due to the vast configurational landscape. Here, we introduce an automated workflow that integrates first-principles physics and atomistic simulations with machine learning (ML), and high-performance computing to allow rapid exploration of the metastable phases of a given elemental composition and construct "metastable" phase diagrams for materials far-from-equilibrium. Using carbon, a prototypical system with a large number of metastable phases without parent in equilibrium, we demonstrate automated metastable phase diagram construction to map hundreds of metastable states ranging from near equilibrium to those far-from-equilibrium (400 meV/atom). Moreover, we incorporate the free energy calculations into a neural-network-based learning of the equations of state that allows for efficient construction of metastable phase diagrams. We use the metastable phase diagram and identify domains of relative stability and synthesizability of metastable materials. High temperature high pressure experiments using a diamond anvil cell on graphite sample coupled with high-resolution transmission electron microscopy (HRTEM) confirm our metastable phase predictions. In particular, we identify the previously ambiguous structure of n-diamond as a cubic-analog of diaphite-like lonsdaelite phase. The workflow presented here is general and broadly applicable to other chemical systems.