  Primordial nucleosynthesis is an observational cornerstone of the Hot Big
Bang model and a sensitive probe of physics beyond the standard model. Its
success has been limited by the so-called Lithium problem, for which many
solutions have been proposed. We report on a self-consistent perturbative
analysis of the effects of variations in nature's fundamental constants, which
are unavoidable in most extensions of the standard model, on primordial
nucleosynthesis, focusing on a broad class of Grand Unified Theory models. A
statistical comparison between theoretical predictions and observational
measurements of ${}^4$He, D, ${}^3$He and, ${}^7$Li consistently yields a
preferred value of the fine-structure constant $\alpha$ at the nucleosynthesis
epoch that is larger than the current laboratory one. The level of statistical
significance and the preferred extent of variation depend on model assumptions
but the former can be more than four standard deviations, while the latter is
always compatible with constraints at lower redshifts. If Lithium is not
included in the analysis, the preference for a variation of $\alpha$ is not
statistically significant. The abundance of ${}^3$He is relatively insensitive
to such variations. Our analysis highlights a viable and physically motivated
solution to the Lithium problem, which warrants further study.
