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 .