Crystal nucleation is facilitated by transient, nanoscale fluctuations that are extraordinarily difficult to observe. Here, we use high-speed atomic force microscopy to directly observe the growth of an aluminum hydroxide film from an aqueous solution and characterize the dynamically fluctuating nanostructures that precede its formation. Nanoscale cluster distributions and fluctuation dynamics show many similarities to the predictions of classical nucleation theory, but the cluster energy landscape deviates from classical expectations. Kinetic Monte Carlo simulations show that these deviations can arise from electrostatic interactions between the clusters and the underlying substrate, which drive microphase separation to create a nanostructured surface phase. This phase can evolve seamlessly from a low-coverage state of fluctuating clusters into a high-coverage nanostructured network, allowing the film to grow without having to overcome classical nucleation barriers.