We derive the formulae for the time variation of the gravitational "constant" G and of the fine structure "constant" \alpha in various models with extra dimensions and analyze their consistency with the available observational data for distant supernovae. We find that the reported variation of \alpha translates into a small variation of G that makes distant supernovae to appear brighter, in contradiction with recent observations of high z supernovae. The significance of these results within the framework of some cosmological scenarios is also discussed. We find, however, that the magnitude of the effect is not large enough to safely discard the models with extra dimensions studied here.