We present the VIMOS Ultra Deep Survey (VUDS), a spectroscopic redshift survey of ~10 000 very faint galaxies to study the main phase of galaxy assembly in 2 < z ≃ 6. The survey covers 1 deg2 in three separate fields: COSMOS, ECDFS, and VVDS-02h, with the selection of targets based on an inclusive combination of photometric redshifts and colour properties. Spectra covering 3650 < λ < 9350 Å are obtained with VIMOS on the ESO-VLT with integration times of 14h. Here we present the survey strategy, target selection, data processing, and the redshift measurement process with an emphasis on the specific methods used to adapt to this high-redshift range. We discuss the spectra quality and redshift reliability and derive a success rate in redshift measurement of 91%, or 74% by limiting the dataset to the most reliable measurements, down to a limiting magnitude iAB = 25. Measurements are performed all the way down to iAB = 27. The mean redshift of the main sample is z ~ 3 and extends over a broad redshift range mainly in 2 < z < 6. At 3 < z < 5, the galaxies cover a wide range of luminosities −23 < MNUV < −20.5, stellar mass 109M⊙ < M∗ < 1011M⊙, and star formation rates 1M⊙/yr < SFR < 103M⊙/yr. We discuss the spectral properties of galaxies using individual as well asstacked spectra. The comparison between spectroscopic and photometric redshifts as well as colour selection demonstrate the effectiveness of our selection scheme. From about ~ 90% of the data analysed so far, we expect to assemble >6000 galaxies with reliable spectroscopic redshifts in 2 < z < 6 when complete. This makes the VUDS the largest survey 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 main phase of galaxy assembly.