Combining an electronic theory with molecular dynamics simulations we present results for the ultrafast structural changes in small clusters. We determine the time scale for the change from the linear to a triangular structure after the photodetachment process Ag$_3^- ightarrow { m Ag}_3$. We show that the time-dependent change of the ionization potential reflects in detail the internal degrees of freedom, in particular coherent and incoherent motion, and that it is sensitive to the initial temperature. We compare with experiment and point out the general significance of our results.