Interior to the orbit of Mercury, between 0.07 and 0.21 AU, is a dynamically stable region where a population of asteroids, known as Vulcanoids, may reside. We present the results from our search for Vulcanoids using archival data from the Heliospheric Imager-1 (HI-1) instrument on NASAs two STEREO spacecraft. Four separate observers independently searched through images obtained from 2008-12-10 to 2009-02-28. Roughly, all Vulcanoids with e<=0.15 and i<=15deg will pass through the HI-1 field of view at least twice during this period. No Vulcanoids were detected. Based on the number of synthetic Vulcanoids added to the data that were detected, we derive a 3 sigma upper limit (i.e. a confidence level >0.997) that there are presently no Vulcanoids larger than 5.7 km in diameter, assuming an R-band albedo of p_R=0.05 and a Mercury-like phase function. The present-day Vulcanoid population, if it exists at all, is likely a small remnant of the hypothetical primordial Vulcanoid population due to the combined effects of collisional evolution and subsequent radiative transport of collisional fragments. If we assume an extant Vulcanoid population with a collisional equilibrium differential size distribution with a power law index of -3.5, our limit implies that there are no more than 76 Vulcanoids larger than 1 km.