We constrain the lifetime of thermally produced heavy neutral leptons (HNLs) from big bang nucleosynthesis. We show that even a small fraction of mesons present in the primeval plasma leads to the overproduction of primordial helium-4. This constrains the lifetime of HNLs to be tau(N) < 0.02 s for masses above the mass of the pion (as compared to 0.1 s reported previously). In combination with accelerator searches, this allows us to put a new lower bound on the HNL masses and define the "bottom line" for HNL searches at the future Intensity Frontier experiments.