Complex systems, which consist of a large number of interacting constituents, often exhibit universal behavior near a phase transition. A slowdown of certain dynamical observables is one such recurring feature found in a vast array of contexts. This phenomenon, known as critical slowing down, is well studied mostly in thermodynamic phase transitions. However, it is less understood in highly nonequilibrium settings, where the time it takes to traverse the phase boundary becomes comparable to the timescale of dynamical fluctuations. Using transient optical spectroscopy and femtosecond electron diffraction, we studied a photo-induced transition of a model charge-density-wave (CDW) compound, LaTe$_3$. We observed that it takes the longest time to suppress the order parameter at the threshold photoexcitation density, where the CDW transiently vanishes. This finding can be quantitatively captured by generalizing the time-dependent Landau theory to a system far from equilibrium. The experimental observation and theoretical understanding of dynamical slowing down may offer insight into other general principles behind nonequilibrium phase transitions in many-body systems.