It has been recently claimed that primordial magnetic fields could relieve the cosmological Hubble tension. We consider the impact of such fields on the formation of the first cosmological objects, mini-halos forming stars, for present-day field strengths in the range of $2times 10^{-12}$ - $2times 10^{-10}$ G. These values correspond to initial ratios of Alven velocity to the speed of sound of $v_a/c_sapprox 0.03 - 3$. We find that when $v_a/c_sll 1$, the effects are modest. However, when $v_asim c_s$, the starting time of the gravitational collapse is delayed and the duration extended as much as by $Delta$z = 2.5 in redshift. When $v_a > c_s$, the collapse is completely suppressed and the mini-halos continue to grow and are unlikely to collapse until reaching the atomic cooling limit. Employing current observational limits on primordial magnetic fields we conclude that inflationary produced primordial magnetic fields could have a significant impact on first star formation, whereas post-inflationary produced fields do not.