We report the discovery of a new ultra-faint dwarf satellite companion of the Milky Way based on the early survey data from the Hyper Suprime-Cam Subaru Strategic Program. This new satellite, Virgo I, which is located in the constellation of Virgo, has been identified as a statistically significant (5.5 sigma) spatial overdensity of star-like objects with a well-defined main sequence and red giant branch in their color-magnitude diagram. The significance of this overdensity increases to 10.8 sigma when the relevant isochrone filter is adopted for the search. Based on the distribution of the stars around the likely main sequence turn-off at r ~ 24 mag, the distance to Virgo I is estimated as 87 kpc, and its most likely absolute magnitude calculated from a Monte Carlo analysis is M_V = -0.8 +/- 0.9 mag. This stellar system has an extended spatial distribution with a half-light radius of 38 +12/-11 pc, which clearly distinguishes it from a globular cluster with comparable luminosity. Thus, Virgo I is one of the faintest dwarf satellites known and is located beyond the reach of the Sloan Digital Sky Survey. This demonstrates the power of this survey program to identify very faint dwarf satellites. This discovery of VirgoI is based only on about 100 square degrees of data, thus a large number of faint dwarf satellites are likely to exist in the outer halo of the Milky Way.