Standard inflationary hot big bang cosmology predicts small fluctuations in the Cosmic Microwave Background (CMB) with isotropic Gaussian statistics. All measurements support the standard theory, except for a few anomalies discovered in the Wilkinson Microwave Anisotropy Probe maps and confirmed recently by the Planck satellite. The Cold Spot is one of the most significant of such anomalies, and the leading explanation of it posits a large void that imprints this extremely cold area via the linear Integrated Sachs-Wolfe (ISW) effect due to the decay of gravitational potentials over cosmic time, or via the Rees-Sciama (RS) effect due to late-time non-linear evolution. Despite several observational campaigns targeting the Cold Spot region, to date no suitably large void was found at higher redshifts $z > 0.3$. Here we report the detection of an $R =(192 pm 15) h^{-1}Mpc$ size supervoid of depth $delta = -0.13 pm 0.03$, and centred at redshift $z = 0.22$. This supervoid, possibly the largest ever found, is large enough to significantly affect the CMB via the non-linear RS effect, as shown in our Lemaitre-Tolman-Bondi framework. This discovery presents the first plausible explanation for any of the physical CMB anomalies, and raises the possibility that local large-scale structure could be responsible for other anomalies as well.