Research on charge-density-wave (CDW) ordered transition-metal dichalcogenides continues to unravel new states of quantum matter correlated to the intertwined lattice and electronic degrees of freedom. Here, we report an inelastic x-ray scattering investigation of the lattice dynamics of the canonical CDW compound $2H$-TaSe$_2$ complemented by angle-resolved photoemission spectroscopy. Our results rule out the central-peak scenario for the CDW transition in $2H$-TaSe$_2$ and provide evidence for a novel precursor phase above the CDW transition temperature $T_{CDW}$. The phase at temperatures between $T^{*}\,(= 128.7\,,\rm{K})$ and $T_{CDW}\,(= 121.3\,\rm{K})$ is characterized by a fully softened phonon mode and medium-range ordered ($ξ_{corr} = 100\,\rm{\mathring{A}}- 200\,\rm{\mathring{A}})$ static CDW domains. Only $T_{CDW}$ is detectable in our photoemission experiments. Thus, $2H$-TaSe$_2$ exhibits structural before electronic static order and emphasizes the important lattice contribution to CDW transitions.