We constrain the lifetime of thermally produced Heavy Neutral Leptons (HNLs) from primordial nucleosynthesis. We show that even a small fraction of mesons present in the primordial plasma leads to the over-production of the primordial helium. This puts an upper bound on the lifetime of HNLs $tau_{N}<0.02$ s for masses $m_{N}>m_{pi}$ (as compared to 0.1 s reported previously). In combination with accelerator searches, this allows us to put a new lower bound on the HNLs masses and defining the bottom line for HNL searches at the future Intensity Frontier experiments.