Rhizobia, the nitrogen-fixing symbionts of legumes, are polyphyletic bacteria distributed in many alpha- and beta-proteobacterial genera. They likely emerged and diversified through independent horizontal transfers of key symbiotic genes. To replay the evolution of a new rhizobium genus under laboratory conditions, the symbiotic plasmid of Cupriavidus taiwanensis was introduced in the plant pathogen Ralstonia solanacearum, and the generated proto-rhizobium was submitted to repeated inoculations to the C. taiwanensis host, Mimosa pudica L. This experiment validated a two-step evolutionary scenario of key symbiotic gene acquisition followed by genome remodeling under plant selection. Nodulation and nodule cell infection were obtained and optimized mainly via the rewiring of regulatory circuits of the recipient bacterium. Symbiotic adaptation was shown to be accelerated by the activity of a mutagenesis cassette conserved in most rhizobia. Investigating mutated genes led us to identify new components of R. solanacearum virulence and C. taiwanensis symbiosis. Nitrogen fixation was not acquired in our short experiment. However, we showed that post-infection sanctions allowed the increase in frequency of nitrogen-fixing variants among a non-fixing population in the M. pudica–C. taiwanensis system and likely allowed the spread of this trait in natura. Experimental evolution thus provided new insights into rhizobium biology and evolution.