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.4 standard deviations lower than the one determined from Type Ia supernovae. The Planck best fit model also predicts lower values of the matter density fraction Om and clustering amplitude S8 compared to those obtained from the Dark Energy Survey Year 1 data. We show that accounting for the enhanced recombination rate due to additional inhomogeneities in the baryon density can solve both the H0 and the S8-Om tensions. The additional baryon inhomogeneities of required magnitude can be induced by small-scale magnetic fields present in the plasma prior to decoupling. 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.