Primordial magnetic field (PMF) is one of the feasible candidates to explain observed large-scale magnetic fields, for example, intergalactic magnetic fields. We present a new mechanism that brings us information about PMFs on small scales based on the abundance of primordial black holes (PBHs). The anisotropic stress of the PMFs can act as a source of the super-horizon curvature perturbation in the early universe. If the amplitude of PMFs is sufficiently large, the resultant density perturbation also has a large amplitude, and thereby, the PBH abundance is enhanced. Since the anisotropic stress of the PMFs is consist of the square of the magnetic fields, the statistics of the density perturbation follows the non-Gaussian distribution. Assuming Gaussian distributions and delta-function type power spectrum for PMFs, based on a Monte-Carlo method, we obtain an approximate probability density function of the density perturbation, and it is an important piece to relate the amplitude of PMFs with the abundance of PBHs. Finally, we place the strongest constraint on the amplitude of PMFs as a few hundred nano-Gauss on $10^{2};{rm Mpc}^{-1} leq kleq 10^{18};{rm Mpc}^{-1}$ where the typical cosmological observations never reach.