Harvesting non-equilibrium hot carriers from photo-excited metal nanoparticles has enabled plasmon-driven photochemical transformations and tunable photodetection with resonant nanoantennas. Despite numerous studies on the ultrafast dynamics of hot electrons, to date, the temporal evolution of hot holes in metal-semiconductor heterostructures remains unknown. An improved understanding of the carrier dynamics in hot-hole-driven systems is needed to help expand the scope of hot-carrier optoelectronics beyond hot-electron-based devices. Here, using ultrafast transient absorption spectroscopy, we show that plasmon-induced hot-hole injection from gold (Au) nanoparticles into the valence band of p-type gallium nitride (p-GaN) occurs within 200 fs, placing hot-hole transfer on a similar timescale as hot-electron transfer. We further observed that the removal of hot holes from below the Au Fermi level exerts a discernible influence on the thermalization of hot electrons above it, reducing the peak electronic temperature and decreasing the electron-phonon coupling time relative to Au samples without a pathway for hot-hole collection. First principles calculations corroborate these experimental observations, suggesting that hot-hole injection modifies the relaxation dynamics of hot electrons in Au nanoparticles through ultrafast modulation of the d-band electronic structure. Taken together, these ultrafast studies substantially advance our understanding of the temporal evolution of hot holes in metal-semiconductor heterostructures and suggest new strategies for manipulating and controlling the energy distributions of hot carriers on ultrafast timescales.