Many plants associate with arbuscular mycorrhizal fungi for nutrient acquisition, while legumes also associate with nitrogen-fixing rhizobial bacteria. Both associations rely on symbiosis signaling and here we show that cereals can perceive lipochitooligosaccharides (LCOs) for activation of symbiosis signaling, surprisingly including Nod factors produced by nitrogen-fixing bacteria. However, legumes show stringent perception of specifically decorated LCOs, that is absent in cereals. LCO perception in plants is activated by nutrient starvation, through transcriptional regulation of Nodulation Signaling Pathway (NSP)1 and NSP2. These transcription factors induce expression of an LCO receptor and act through the control of strigolactone biosynthesis and the karrikin-like receptor DWARF14-LIKE. We conclude that LCO production and perception is coordinately regulated by nutrient starvation to promote engagement with mycorrhizal fungi. Our work has implications for the use of both mycorrhizal and rhizobial associations for sustainable productivity in cereals.