Magnetic fields play an important role for the formation of stars in both local and high-redshift galaxies. Recent studies of dynamo amplification in the first dark matter haloes suggest that significant magnetic fields were likely present during the formation of the first stars in the Universe at redshifts of 15 and above. In this work, we study how these magnetic fields potentially impact the initial mass function (IMF) of the first stars. We perform 200 high-resolution, three-dimensional (3D), magneto-hydrodynamic (MHD) simulations of the collapse of primordial clouds with different initial turbulent magnetic field strengths as predicted from turbulent dynamo theory in the early Universe, forming more than 1100 first stars in total. We detect a strong statistical signature of suppressed fragmentation in the presence of strong magnetic fields, leading to a dramatic reduction in the number of first stars with masses low enough that they might be expected to survive to the present day. Additionally, strong fields shift the transition point where stars go from being mostly single to mostly multiple to higher masses. However, irrespective of the field strength, individual simulations are highly chaotic, show different levels of fragmentation and clustering, and the outcome depends on the exact realisation of the turbulence in the primordial clouds. While these are still idealised simulations that do not start from cosmological initial conditions, our work shows that magnetic fields play a key role for the primordial IMF, potentially even more so than for the present-day IMF.