Many publications highlight the importance of nitric oxide (NO) in plant–bacteria interactions, either in the promotion of health and plant growth or in pathogenesis. However, the role of NO in the signaling between bacteria and plants and in the fate of their interaction, as well as the reconstruction of their interactive evolution, remains largely unknown. Despite the complexity of the evolution of life on Earth, we explore the hypothesis that denitrification and aerobic respiration were responsible for local NO accumulation, which triggered primordial antagonistic biotic interactions, namely the first phytopathogenic interactions. N-oxides, including NO, could globally accumulate via lightning synthesis in the early anoxic ocean and constitute pools for the evolution of denitrification, considered an early step of the biological nitrogen cycle. Interestingly, a common evolution may be proposed for components of denitrification and aerobic respiration pathways, namely for NO and oxygen reductases, a theory compatible with the presence of low amounts of oxygen before the great oxygenation event (GOE), which was generated by Cyanobacteria. During GOE, the increase in oxygen caused the decrease of Earth’s temperature and the consequent increase of oxygen dissolution and availability, making aerobic respiration an increasingly dominant trait of the expanding mesophilic lifestyle. Horizontal gene transfer was certainly important in the joint expansion of mesophily and aerobic respiration. First denitrification steps lead to NO formation through nitrite reductase activity, and NO may further accumulate when oxygen binds NO reductase, resulting in denitrification blockage. The consequent transient NO surplus in an oxic niche could have been a key factor for a successful outcome of an early denitrifying prokaryote able to scavenge oxygen by NO/oxygen reductase or by an independent heterotrophic aerobic respiration pathway. In fact, NO surplus could result in toxicity causing “the first disease” in oxygen-producing Cyanobacteria. We inspected in bacteria the presence of sequences similar to the NO-producing nitrite reductase nirS gene of Thermus thermophilus, an extreme thermophilic aerobe of the Thermus/Deinococcus group, which constitutes an ancient lineage related to Cyanobacteria. In silico analysis revealed the relationship between the presence of nirS genes and phytopathogenicity in Gram-negative bacteria.