In the primordial Big Bang nucleosynthesis (BBN), only the lightest nuclides (D, $^3$He, $^4$He, and $^7$Li) were synthesized in appreciable quantities, and these relics provide us a unique window on the early universe. Currently, BBN simulations give acceptable agreement between theoretical and observed abundances of D and $^4$He, but it is still difficult to reconcile the predicted $^7$Li abundance with the observation for the Galactic halo stars. The BBN model overestimates the primordial $^7$Li abundance by about a factor of three, so called the cosmological lithium problem, a long-lasting pending issue in BBN. Great efforts have been paid in the past decades, however, the conventional nuclear physics seems unable to resolve such problem. It is well-known that the classical Maxwell-Boltzmann (MB) velocity distribution has been usually assumed for nuclei in the Big-Bang plasma. In this work, we have thoroughly investigated the impact of non-extensive Tsallis statistics (deviating from the MB) on thermonuclear reaction rates involved in standard models of BBN. It shows that the predicted primordial abundances of D, $^4$He, and $^7$Li agree very well with those observed ones by introducing a non-extensive parameter $q$. It is discovered that the velocities of nuclei in a hot Big-Bang plasma indeed violate the classical Maxwell-Boltzmann (MB) distribution in a very small deviation of about 6.3--8.2%. Thus, we have for the first time found a new solution to the cosmological lithium problem without introducing any mysterious theories. Furthermore, the implications of non-extensive statistics in other exotic high-temperature and density astrophysical environments should be explored, which might offer new insight into the nucleosynthesis of heavy elements.