The standard cosmological model determined from the accurate cosmic microwave background measurements made by the Planck satellite implies a value of the Hubble constant H0 that is 4.2 standard deviations lower than the one determined from Type Ia supernovae. The Planck best fit model also predicts higher values of the matter density fraction Omega_m and clustering amplitude S8 compared to those obtained from the Dark Energy Survey Year 1 data. Here we show that accounting for the enhanced recombination rate due to additional small-scale inhomogeneities in the baryon density may solve both the H0 and the S8-Omega_m tensions. The additional baryon inhomogeneities can be induced by primordial magnetic fields present in the plasma prior to recombination. The required field strength to solve the Hubble tension is just what is needed to explain the existence of galactic, cluster, and extragalactic magnetic fields without relying on dynamo amplification. Our results show clear evidence for this effect and motivate further detailed studies of primordial magnetic fields, setting several well-defined targets for future observations.