We present the VIMOS Ultra Deep Survey (VUDS), a spectroscopic redshift survey of ~10.000 very faint galaxies to study the major phase of galaxy assembly 2<z<~6. The survey covers 1 deg^2 in 3 separate fields: COSMOS, ECDFS and VVDS-02h, with targets selection based on an inclusive combination of photometric redshifts and color properties. Spectra covering 3650<lambda<9350 A are obtained with VIMOS on the ESO-VLT with integration times of 14h. Here we present the survey strategy, the target selection, the data processing, as well as the redshift measurement process, emphasizing the specific methods adapted to this high redshift range. The spectra quality and redshift reliability are discussed, and we derive a completeness in redshift measurement of 91%, or 74% for the most reliable measurements, down to i_AB=25, and measurements are performed all the way down to i_AB=27. The redshift distribution of the main sample peaks at z=3-4 and extends over a large redshift range mainly in 2 < z < 6. At 3<z<5, the galaxies cover a large range of luminosities -23< M_U < -20.5, stellar mass 10^9 M_sun< M_star < 10^{11} M_sun, and star formation rates 1 M_sun/yr< SFR < 10^3 M_sun/yr. We discuss the spectral properties of galaxies using individual as well as stacked spectra. The comparison between spectroscopic and photometric redshifts as well as color selection demonstrate the effectiveness of our selection scheme. With ~6000 galaxies with reliable spectroscopic redshifts in 2<z<6 expected when complete, this survey is the largest at these redshifts and offers the opportunity for unprecedented studies of the star-forming galaxy population and its distribution in large scale structures during the major phase of galaxy assembly.