An inhomogeneous cosmological magnetic field creates vortical perturbations that survive Silk damping on much smaller scales than compressional modes . This ensures that there is no sharp cut-off in anisotropy on arc-minute scales . As we had pointed out earlier , tangled magnetic fields , if they exist , will then be a potentially important contributor to small-angular scale CMBR anisotropies . Several ongoing and new experiments , are expected to probe the very small angular scales , corresponding to multipoles with l > 1000 . In view of this observational focus , we revisit the predicted signals due to primordial tangled magnetic fields , for different spectra and different cosmological parameters . We also identify a new regime , where the photon mean-free path exceeds the scale of the perturbation , which dominates the predicted signal at very high l . A scale-invariant spectrum of tangled fields which redshifts to a present value B _ { 0 } = 3 \times 10 ^ { -9 } Gauss , produces temperature anisotropies at the 10 \mu K level between l \sim 1000 - 3000 . Larger signals result if the univese is lambda dominated , if the baryon density is larger , or if the spectral index of magnetic tangles is steeper , n > -3 . The signal will also have non-Gaussian statistics . We predict the distinctive form of the increased power expected in the microwave background at high l in the presence of significant tangled magnetic fields . We may be on the verge of detecting or ruling out the presence of tangled magnetic fields which are strong enough to influence the formation of large-scale structure in the Universe .