Nodulin proteins are expressed in legume root cells after infection with rhizobia. Nodulins have been classified as early and late, reflecting the developmental time points of their expression. Leghemoglobin (LegH), which is a classical example of a late nodulin, sequesters oxygen inside the nodule to protect the nitrogenase from oxygen toxicity to sustain symbiotic nitrogen fixation (SNF). Post-translational modification and/or protein–protein interaction are known to regulate activity of proteins. To elucidate the role of post-translational modification of LegH on its oxygen sequestration activity, earlier we have shown that phosphorylation at its S45 imparts most structural disruption of the porphyrin binding pocket responsible for its oxygen binding. In the present report, in an attempt to characterize the protein(s) that may interact with LegH to regulate its activity, it is demonstrated that LegH interact in vitro with Nodulin 16 of Lotus japonicus (Nlj16), another late nodulin. These two interacting proteins resulted in a bigger sized particle which shows higher diffusion coefficient as measured by dynamic light scattering. Interestingly, it was also shown that in vitro oxygen sequestration by LegH is stimulated by this interaction. Furthermore, this interaction is validated by the fact that LegH and Nlj16 could be co-immunoprecipitated from the nodule lysate. Most importantly, fluorescent immunohistochemistry of post-infected nodule sections show perceivable co-localization of these two proteins in the nodule symbiosomes. Thus, this work is a foundation for further investigation on these two interacting late nodulins as one of the plausible regulations for the oxygen sequestration by LegH during SNF.