Engineering nitrogen fixation in eukaryotes requires high expression of functional nitrogenase structural proteins, a goal that has not yet been achieved. Here we build a knowledge-based library containing 32 nitrogenase nifH sequences from prokaryotes of diverse ecological niches and metabolic features and combine with rapid screening in tobacco to identify superior NifH variants for plant mitochondria expression. Three NifH variants outperform in tobacco mitochondria and are further tested in yeast. Hydrogenobacter thermophilus (Aquificae) NifH is isolated in large quantities from yeast mitochondria and fulfills NifH protein requirements for efficient N2 fixation, including electron transfer for substrate reduction, P-cluster maturation, and FeMo-co biosynthesis. H. thermophilus NifH expressed in tobacco leaves shows lower nitrogenase activity than that from yeast. However, transfer of [Fe4S4] clusters from NifU to NifH in vitro increases 10-fold the activity of the tobacco-isolated NifH, revealing that plant mitochondria [Fe-S] cluster availability constitutes a bottleneck to engineer plant nitrogenases.