The NRAO VLA Sky Survey (NVSS) is the only dataset that allows an accurate determination of the auto-correlation function (ACF) on angular scales of several degrees for Active Galactic Nuclei (AGNs) at typical redshifts $z \simeq 1$. Surprisingly, the ACF is found to be positive on such large scales while, in the framework of the standard hierarchical clustering scenario with Gaussian primordial perturbations it should be negative for a redshift-independent effective halo mass of order of that found for optically-selected quasars. We show that a small primordial non-Gaussianity can add sufficient power on very large scales to account for the observed NVSS ACF. The best-fit value of the parameter $f_{\rm NL}$, quantifying the amplitude of primordial non-Gaussianity of local type is $f_{\rm NL}=62 \pm 27$ ($1\,\sigma$ error bar) and $25<f_{\rm NL}<117$ ($2\,\sigma$ confidence level), corresponding to a detection of non-Gaussianity significant at the $\sim 3\,\sigma$ confidence level. The minimal halo mass of NVSS sources is found to be $M_{\rm min}=10^{12.47\pm0.26}h^{-1}M_{\odot}$ ($1\,\sigma$) strikingly close to that found for optically selected quasars. We discuss caveats and possible physical and systematic effects that can impact on the results.