Ultrafast photoinduced phase transitions could revolutionize data-storage and telecommunications technologies by modulating signals in integrated nanocircuits at terahertz speeds. In quantum phase-changing materials (PCMs), microscopic charge, lattice, and orbital degrees of freedom interact cooperatively to modify macroscopic electrical and optical properties. Although these interactions are well documented for bulk single crystals and thin films, little is known about the ultrafast dynamics of nanostructured PCMs when interfaced to another class of materials as in this case to active plasmonic elements. Here, we demonstrate how a mesh of gold nanoparticles, acting as a plasmonic photocathode, induces an ultrafast phase transition in nanostructured vanadium dioxide (VO2) when illuminated by a spectrally resonant femtosecond laser pulse. Hot electrons created by optical excitation of the surface-plasmon resonance in the gold nanomesh are injected ballistically across the Au/VO2 interface to induce a subpicosecond phase transformation in VO2. Density functional calculations show that a critical density of injected electrons leads to a catastrophic collapse of the 6 THz phonon mode, which has been linked in different experiments to VO2 phase transition. The demonstration of subpicosecond phase transformations that are triggered by optically induced electron injection opens the possibility of designing hybrid nanostructures with unique nonequilibrium properties as a critical step for all-optical nanophotonic devices with optimizable switching thresholds.