Primordial magnetic fields lead to non-Gaussian signals in the Cosmic Microwave Background (CMB) even at the lowest order, as magnetic stresses, and the temperature anisotropy they induce, depend quadratically on the magnetic field. In contrast, CMB non-Gaussianity due to inflationary scalar perturbations arise only as a higher order effect. We propose here a novel probe of stochastic primordial magnetic fields that exploits the characteristic CMB non-Gaussianity that they induce. In particular, we compute the CMB bispectrum ($b_{l_{_1}l_{_2}l_{_3}}$) induced by stochastic primordial fields on large angular scales. We find a typical value of $l_1(l_1+1)l_3(l_3+1) b_{l_{_1}l_{_2}l_{_3}} sim 10^{-22}$, for magnetic fields of strength $B_0 sim 3$ nano Gauss and with a nearly scale invariant magnetic spectrum. Current observational limits on the bispectrum allow us to set upper limits on $B_0 sim 35$ nano Gauss, which can be improved by including other magnetically induced contributions to the bispectrum.