A population of very light primordial black holes which evaporate before nucleosynthesis begins is unconstrained unless the decaying black holes leave stable relics. We show that gravitons Hawking radiated from these black holes would source a substantial stochastic background of high frequency gravititational waves (10(12) Hz or more) in the present Universe. These black holes may lead to a transient period of matter-dominated expansion. In this case the primordial Universe could be temporarily dominated by large clusters of "Hawking stars" and the resulting gravitational wave spectrum is independent of the initial number density of primordial black holes.