In legume-rhizobia symbiosis, partner recognition and the initiation of symbiosis processes require the mutual exchange of chemical signals. Chemicals, generally (iso)flavonoids, in the root exudates of the host plant induce the expression of nod genes in rhizobia, and, thus, are called nod gene inducers. The expression of nod genes leads to the production of lipochitooligosaccharides (LCOs) called Nod factors. Natural nod gene inducer(s) in Lotus japonicus-Mesorhizobium symbiosis remain unknown. Therefore, we developed an LCO detection method based on ultra-high-performance liquid chromatography-tandem-quadrupole mass spectrometry (UPLC-TQMS) to identify these inducers and used it herein to screen 40 phenolic compounds and aldonic acids for their ability to induce LCOs in Mesorhizobium japonicum MAFF303099. We identified five phenolic acids with LCO-inducing activities, including p-coumaric, caffeic, and ferulic acids. The induced LCOs caused root hair deformation, and nodule numbers in L. japonicus inoculated with M. japonicum were increased by these phenolic acids. The three phenolic acids listed above induced the expression of the nodA, nodB, and ttsI genes in a strain harboring a multicopy plasmid encoding NodD1, but not that encoding NodD2. The presence of p-coumaric and ferulic acids in the root exudates of L. japonicus was confirmed by UPLC-TQMS, and the induction of ttsI::lacZ in the strain harboring the nodD1 plasmid was detected in the rhizosphere of L. japonicus. Based on these results, we propose that phenolic acids are a novel type of nod gene inducer in L. japonicus-Mesorhizobium symbiosis.