Abstract Symbiosis between cyanobacteria and plants is considered pivotal for biological nitrogen deposition in terrestrial ecosystems. Despite extensive knowledge of the ecology of plant–cyanobacterium symbioses, little is known about the molecular mechanisms involved in recognition between partners. Here, we conducted a quantitative sequential window acquisition of all theoretical fragment ion spectra mass spectrometry pipeline to analyze protein changes in Oryza sativa and Nostoc punctiforme during early events of symbiosis. We found differentially expressed proteins in both organisms linked to several biological functions, including signal transduction, adhesion, defense-related proteins and cell wall modification. In N. punctiforme we found increased expression of 62 proteins that have been previously described in other Nostoc–plant symbioses, reinforcing the robustness of our study. Our findings reveal new proteins activated in the early stages of the Nostoc–Oryza symbiosis that might be important for the recognition between the plant and the host. Oryza mutants in genes in the common symbiosis signaling pathway (CSSP) show reduced colonization efficiency, providing first insights on the involvement of the CSSP for the accommodation of N. punctiforme inside the plant cells. This information may have long-term implications for a greater understanding of the symbiotic interaction between Nostoc and land plants.