Quasi-two-dimensional transition metal dichalcogenides (TMDs) are a key platform for exploring emergent nanoscale phenomena arising from complex interactions. Access to the underlying degrees of freedom on their natural time scales motivates the use of advanced ultrafast probes that directly couple to the self-organised electronic and atomic structural order. Here, we report the first ultrafast investigation of TaTe2, which exhibits unique charge and lattice structural order characterised by a transition upon cooling from stripe-like trimer chains into a $(3 times 3)$ superstructure of trimer clusters. Utilising MeV-scale ultrafast electron diffraction, the TaTe2 structural dynamics is resolved following intense pulsed laser excitation at 1.2 eV. We observe a rapid $approx!1.4$ ps melting of the low-temperature ordered state, followed by recovery of the clusters via thermalisation into a hot superstructure persisting for extended times. Density-functional calculations indicate that the initial quench is triggered by Ta trimer bonding to nonbonding transitions that destabilises the clusters, unlike melting of charge density waves in other TaX2 compounds. Our work paves the way for further exploration and ultimately directed manipulation of the trimer superstructure for novel applications.