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-CamSubaru 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 objectswith a well-defined main sequence and red giant branch in a color-magnitude diagram. Based on the distribution of the stars around the likely mainsequence turn-off, the distance to Virgo I is estimated as 87 kpc,suggesting an absolute magnitude of $M_V = -0.23^{+0.25}_{-1.67}$~mag.This stellar system has an extended spatial distribution with a half-light radius of 38$^{+12}_{-11}$~pc, which clearly distinguishesit 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 Virgo I 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.