Sinorhizobium meliloti is a gram-negative α-proteobacterium with the ability to develop nitrogen-fixing root nodules with legumes of the genera Medicago, Melilotus, and Trigonella. These symbiotic associations are tightly regulated, and rhizobial strains compete in soil for the colonization of the limited symbiotic niche. Thus, different rhizobial isolates with diverse nitrogen-fixing capacities compete with each other for root-nodule occupancy. Current evidence indicates that symbiotic competitiveness for nodule occupancy is a complex phenomenon, and that early processes in the rhizosphere are determinant to define which strains will finally associate with the host plant. Unfortunately, the molecular characterization of early events in the rhizosphere by classical transcriptomics and proteomics is technically challenging mainly due to the low numbers of colonizing rhizobia. In order to search for rhizobial genes that are required for an efficient root colonization we used STM technologies coupled to high throughput second-generation DNA sequencing. The achieved results allowed us to identify more than one hundred S. meliloti genes whose interruption generates negative effects on the colonization of alfalfa roots. Affected mutants could be grouped according to their growth in reach medium, minimal medium, and root exudates. Affection in root colonization strongly correlated with the proportion of nodule occupancy late in symbiosis. Thus, the presence and expression of the identified gene set will be a valuable tool at the time of screening for new inoculant rhizobia. Finally, the comparison of the gene sets required for the colonization of homologous vs. heterologous plants allowed us to draw out general conclusions about the evolutionary origin of the main genetic markers and functions associated with the specific colonization of the host-plant root.