Salt stress is an important abiotic stress that causes decreased crop yields. Root growth and plant activities are affected by salt stress through the actions of specific genes that help roots adapt to adverse environmental conditions. For a more comprehensive understanding of proteins affected by salinity, we used two-dimensional gel electrophoresis and mass spectrometry to characterize the proteome-level changes associated with salt stress response in Medicago sativa cv. Zhongmu-1 and Medicago truncatula cv. Jemalong A17 roots. Our physiological and phenotypic observations indicated that Zhongmu-1 was more salt tolerant than Jemalong A17. We identified 93 and 30 proteins whose abundance was significantly affected by salt stress in Zhongmu-1 and Jemalong A17 roots, respectively. The tandem mass spectrometry analysis of the differentially accumulated proteins resulted in the identification of 60 and 26 proteins in Zhongmu-1 and Jemalong A17 roots, respectively. Function analyses indicated molecule binding and catalytic activity were the two primary functional categories. These proteins have known functions in various molecular processes, including defense against oxidative stress, metabolism, photosynthesis, protein synthesis and processing, and signal transduction. The transcript levels of four identified proteins were determined by quantitative reverse transcription polymerase chain reaction. Our results indicate that some of the identified proteins may play key roles in salt stress tolerance.