The Virgo Environmental Survey Tracing Ionised Gas Emission (VESTIGE) is a blind narrow-band Halpha+[NII] imaging survey carried out with MegaCam at the Canada-France-Hawaii Telescope. The survey covers the whole Virgo cluster region from its core to one virial radius (104 deg^2). The sensitivity of the survey is of f(Halpha) ~ 4 x 10^-17 erg sec-1 cm^-2 (5 sigma detection limit) for point sources and Sigma (Halpha) ~ 2 x 10^-18 erg sec^-1 cm^-2 arcsec^-2 (1 sigma detection limit at 3 arcsec resolution) for extended sources, making VESTIGE the deepest and largest blind narrow-band survey of a nearby cluster. This paper presents the survey in all its technical aspects, including the survey design, the observing strategy, the achieved sensitivity in both the narrow-band Halpha+[NII] and in the broad-band r filter used for the stellar continuum subtraction, the data reduction, calibration, and products, as well as its status after the first observing semester. We briefly describe the Halpha properties of galaxies located in a 4x1 deg^2 strip in the core of the cluster north of M87, where several extended tails of ionised gas are detected. This paper also lists the main scientific motivations of VESTIGE, which include the study of the effects of the environment on galaxy evolution, the fate of the stripped gas in cluster objects, the star formation process in nearby galaxies of different type and stellar mass, the determination of the Halpha luminosity function and of the Halpha scaling relations down to ~ 10^6 Mo stellar mass objects, and the reconstruction of the dynamical structure of the Virgo cluster. This unique set of data will also be used to study the HII luminosity function in hundreds of galaxies, the diffuse Halpha+[NII] emission of the Milky Way at high Galactic latitude, and the properties of emission line galaxies at high redshift.