A key goal of the Stage IV dark energy experiments Euclid, LSST and WFIRST is to measure the growth of structure with cosmic time from weak lensing analysis over large regions of the sky. Weak lensing cosmology will be challenging: in addition to highly accurate galaxy shape measurements, statistically robust and accurate photometric redshift (photo-z) estimates for billions of faint galaxies will be needed in order to reconstruct the three-dimensional matter distribution. Here we present an overview of and initial results from the Complete Calibration of the Color-Redshift Relation (C3R2) survey, designed specifically to calibrate the empirical galaxy color-redshift relation to the Euclid depth. These redshifts will also be important for the calibrations of LSST and WFIRST. The C3R2 survey is obtaining multiplexed observations with Keck (DEIMOS, LRIS, and MOSFIRE), the Gran Telescopio Canarias (GTC; OSIRIS), and the Very Large Telescope (VLT; FORS2 and KMOS) of a targeted sample of galaxies most important for the redshift calibration. We focus spectroscopic efforts on under-sampled regions of galaxy color space identified in previous work in order to minimize the number of spectroscopic redshifts needed to map the color-redshift relation to the required accuracy. Here we present the C3R2 survey strategy and initial results, including the 1283 high confidence redshifts obtained in the 2016A semester and released as Data Release 1.