Continuing our program of spectroscopic observations of International Celestial Reference Frame (ICRF) sources, we present redshifts for 120 quasars and radio galaxies. Data were obtained with five telescopes: the 3.58m European Southern Observatory New Technology Telescope, the two 8.2m Gemini telescopes, the 2.5m Nordic Optical Telescope (NOT), and the 6.0m Big Azimuthal Telescope of the Special Astrophysical Observatory in Russia. The targets were selected from the International VLBI Service for Geodesy & Astrometry candidate International Celestial Reference Catalog which forms part of an observational very long baseline interferometry (VLBI) program to strengthen the celestial reference frame. We obtained spectra of the potential optical counterparts of more than 150 compact flat-spectrum radio sources, and measured redshifts of 120 emission-line objects, together with 19 BL Lac objects. These identifications add significantly to the precise radio-optical frame tie to be undertaken by Gaia, due to be launched in 2013, and to the existing data available for analyzing source proper motions over the celestial sphere. We show that the distribution of redshifts for ICRF sources is consistent with the much larger sample drawn from Faint Images of the Radio Sky at Twenty cm (FIRST) and Sloan Digital Sky Survey, implying that the ultra-compact VLBI sources are not distinguished from the overall radio-loud quasar population. In addition, we obtained NOT spectra for five radio sources from the FIRST and NRAO VLA Sky Survey catalogs, selected on the basis of their red colors, which yielded three quasars with z>4.