We investigate the ultrafast structural dynamics of NbTe₂ following photoexcitation using ultrafast electron diffraction, transient reflectivity, and Raman spectroscopy. Ultrafast electron diffraction measurements record the cooperative atomic motions leading to the weakened CDW order, while transient reflectivity measurements reveal coherent phonon oscillations that evolve with increasing fluence, highlighting modifications to the electronic potential. Above a threshold, a non-thermal melting of the (3×1×3) CDW phase occurs stochastically at specific nucleation sites and the sample undergoes a recrystallization into a stable high-fluence (HF) phase, characterized by a distinct set of phonon modes observed via Raman spectroscopy. These findings provide insights into photoinduced phase transitions and potential for laser-driven engineering of structural states in quantum materials.