Various endophytic rhizobacteria promote the growth of cereal crops. To achieve a better understanding of the cellular and molecular bases of beneficial cereal-rhizobia interactions, we performed computer-assisted microscopy and transcriptomic analyses of rice seedling shoots (Oryza sativa) during early stages of endophytic colonization by the plant growth-promoting Sinorhizobium meliloti 1021. Phenotypic analyses revealed that plants inoculated with live rhizobia had increased shoot height and dry weight compared to control plants inoculated with heat-killed cells of the same microbe. At 6 days after inoculation (DAI) with live cells, the fourth-leaf sheaths showed significant cytological differences including their enlargement of parenchyma cells and reduction in shape complexity. Transcriptomic analysis of shoots identified 2,414 differentially-expressed genes (DEGs) at 1, 2, 5 and 8 DAI: 195, 1390, 1025 and 533, respectively. Among these, 46 DEGs encoding cell-cycle functions were up-regulated at least 3 days before the rhizobia ascended from the roots to the shoots, suggesting that rhizobia are engaged in long-distance signaling events during early stages of this plant-microbe interaction. DEGs involved in phytohormone production, photosynthetic efficiency, carbohydrate metabolism, cell division and wall expansion were significantly elevated at 5 and 8 DAI, consistent with the observed phenotypic changes in rice cell morphology and shoot growth-promotion. Correlation analysis identified 104 height-related DEGs and 120 dry-weight-related DEGs that represent known quantitative-trait loci for seedling vigor and increased plant height. These findings provide multiple evidences of plant–microbe interplay that give insight into the growth-promotion processes associated with this rhizobia-rice beneficial association.