Phase transitions in equilibrium and nonequilibrium systems play a major role in the natural sciences. In dynamical networks, phase transitions organize qualitative changes in the collective behavior of coupled dynamical units. Adaptive dynamical networks feature a connectivity structure that changes over time, coevolving with the nodes' dynamical state. In this Letter, we show the emergence of two distinct first-order nonequilibrium phase transitions in a finite-size adaptive network of heterogeneous phase oscillators. Depending on the nature of defects in the internal frequency distribution, we observe either an abrupt single-step transition to full synchronization or a more gradual multistep transition. This observation has a striking resemblance to heterogeneous nucleation. We develop a mean-field approach to study the interplay between adaptivity and nodal heterogeneity and describe the dynamics of multicluster states and their role in determining the character of the phase transition. Our work provides a theoretical framework for studying the interplay between adaptivity and nodal heterogeneity.