The genus Rhizobium contains many species that are able to form nitrogen-fixing nodules on plants of the legume family. Here, we report the 5.5-Mb draft genome sequence of the salt-tolerant Rhizobium sp. strain LCM 4573, which has a G+C content of 61.2% and 5,356 candidate protein-encoding genes.