The Next Generation Virgo Cluster Survey is an optical imaging survey covering 104 deg^2 centered on the Virgo cluster. Currently, the complete survey area has been observed in the u*giz-bands and one third in the r-band. We present the photometric redshift estimation for the NGVS background sources. After a dedicated data reduction, we perform accurate photometry, with special attention to precise color measurements through point spread function-homogenization. We then estimate the photometric redshifts with the Le Phare and BPZ codes. We add a new prior which extends to iAB = 12.5 mag. When using the u*griz-bands, our photometric redshifts for 15.5 le i lesssim 23 mag or zphot lesssim 1 galaxies have a bias |Delta z| < 0.02, less than 5% outliers, and a scatter sigma_{outl.rej.} and an individual error on zphot that increase with magnitude (from 0.02 to 0.05 and from 0.03 to 0.10, respectively). When using the u*giz-bands over the same magnitude and redshift range, the lack of the r-band increases the uncertainties in the 0.3 lesssim zphot lesssim 0.8 range (-0.05 < Delta z < -0.02, sigma_{outl.rej} ~ 0.06, 10-15% outliers, and zphot.err. ~ 0.15). We also present a joint analysis of the photometric redshift accuracy as a function of redshift and magnitude. We assess the quality of our photometric redshifts by comparison to spectroscopic samples and by verifying that the angular auto- and cross-correlation function w(theta) of the entire NGVS photometric redshift sample across redshift bins is in agreement with the expectations.