We present the results of a program to acquire high-quality optical spectra of X-ray sources detected in the E-CDF-S and its central area. New spectroscopic redshifts are measured for 283 counterparts to Chandra sources with deep exposures (t~2-9 hr per pointing) using multi-slit facilities on both the VLT and Keck thus bringing the total number of spectroscopically-identified X-ray sources to over 500 in this survey field. We provide a comprehensive catalog of X-ray sources detected in the E-CDF-S including the optical and near-infrared counterparts, and redshifts (both spectroscopic and photometric) that incorporate published spectroscopic catalogs thus resulting in a final sample with a high fraction (80%) of X-ray sources having secure identifications. We demonstrate the remarkable coverage of the Lx-z plane now accessible from our data while emphasizing the detection of AGNs that contribute to the faint end of the luminosity function at 1.5<z<3. Our redshift catalog includes 17 type 2 QSOs that significantly increases such samples (2x). With our deepest VIMOS observation, we identify "elusive" optically-faint galaxies (R~25) at z~2-3 based upon the detection of interstellar absorption lines; we highlight one such case, an absorption-line galaxy at z=3.208 having no obvious signs of an AGN in its optical spectrum. In addition, we determine distances to eight galaxy groups with extended X-ray emission. Finally, we measure the physical extent of known large-scale structures (z~0.7) evident in the CDF-S. While a thick sheet (radial size of 67.7 Mpc) at z~0.67 extends over the full field, the z~0.73 structure is thin (18.8 Mpc) and filamentary as traced by both AGNs and galaxy groups. In the appendix, we provide spectroscopic redshifts for 49 counterparts to fainter X-ray sources detected only in the 1 and 2 Ms catalogs, and 48 VLA radio sources not detected in X-rays.