We study the properties of a sample of 211 heavily-obscured Active Galactic Nucleus (AGN) candidates in the Extended Chandra Deep Field-South selecting objects with f_24/f_R>1000 and R-K>4.5. Of these, 18 were detected in X-rays and found to be obscured AGN with neutral hydrogen column densities of ~10^23 cm^-2. In the X-ray undetected sample, the following evidence suggests a large fraction of heavily-obscured (Compton Thick) AGN: (i) The stacked X-ray signal of the sample is strong, with an observed ratio of soft to hard X-ray counts consistent with a population of ~90% heavily obscured AGN combined with 10% star-forming galaxies. (ii) The X-ray to mid-IR ratios for these sources are significantly larger than that of star-forming galaxies and ~2 orders of magnitude smaller than for the general AGN population, suggesting column densities of N_H>5x10^24 cm^-2. (iii) The Spitzer near- and mid-IR colors of these sources are consistent with those of the X-ray-detected sample if the effects of dust self-absorption are considered. Spectral fitting to the rest-frame UV/optical light (dominated by the host galaxy) returns stellar masses of ~10^11 M_sun and <E(B-V)> =0.5, and reveals evidence for a significant young stellar population, indicating that these sources are experiencing considerable star-formation. This sample of heavily-obscured AGN candidates implies a space density at z~2 of ~10^-5 Mpc^-3, finding a strong evolution in the number of L_X>10^44 erg/s sources from z=1.5 to 2.5, possibly consistent with a short-lived heavily-obscured phase before an unobscured quasar is visible.