We provide the most stringent constraint to date on possible deviations from the usually-assumed Maxwell-Boltzmann (MB) velocity distribution for nuclei in the Big-Bang plasma. The impact of non-extensive Tsallis statistics on thermonuclear reaction rates involved in standard models of Big-Bang Nucleosynthesis (BBN) has been investigated. We find that the non-extensive parameter $q$ may deviate by, at most, $|\delta q|$=6$\times$10$^{-4}$ from unity for BBN predictions to be consistent with observed primordial abundances; $q$=1 represents the classical Boltzmann-Gibbs statistics. This constraint arises primarily from the {\em super}sensitivity of endothermic rates on the value of $q$, which is found for the first time. As such, the implications of non-extensive statistics in other astrophysical environments should be explored. This may offer new insight into the nucleosynthesis of heavy elements.