We use holography to develop a physical picture of the real-time evolution of the spinodal instability of a four-dimensional, strongly-coupled gauge theory with a first-order, thermal phase transition. We numerically solve Einstein's equations to follow the evolution, in which we identify four generic stages: a first, linear stage in which the instability grows exponentially; a second, non-linear stage in which peaks and/or phase domains are formed; a third stage in which these structures merge; and a fourth stage in which the system finally relaxes to a static, phase-separated configuration. On the gravity side the latter is described by a static, stable, inhomogeneous horizon. We conjecture and provide evidence that all static, non-phase separated configurations in large enough boxes are dynamically unstable. We show that all four stages are well described by the constitutive relations of second-order hydrodynamics that include all second-order gradients that are purely spatial in the local rest frame. In contrast, a Müller-Israel-Stewart-type formulation of hydrodynamics fails to provide a good description for two reasons. First, it misses some large, purely-spatial gradient corrections. Second, several second-order transport coefficients in this formulation, including the relaxation times τπ and τΠ, diverge at the points where the speed of sound vanishes.