Motivated by the fact that the Next-to-Minimal Supersymmetric Standard Model is one of the most plausible models that can accommodate electroweak baryogenesis, we analyze its phase structure by tracing the temperature dependence of the minima of the effective potential. Our results reveal rich patterns of phase structure that end in the observed electroweak symmetry breaking vacuum. We classify these patterns according to the first transition in their history and show the strong first-order phase transitions that may be possible in each type of pattern. These could allow for the generation of the matter-antimatter asymmetry or potentially observable gravitational waves. For a selection of benchmark points, we checked that the phase transitions completed and calculated the nucleation temperatures. We furthermore present samples that feature strong first-order phase transitions from an extensive scan of the whole parameter space. We highlight common features of our samples, including the fact that the Standard Model like Higgs is often not the lightest Higgs in the model.