Knowledge of the extent of variation in a species is crucial for successful exploitation of its natural genetic diversity. Our goals were to evaluate the genetic diversity in the collection of the model legume species Medicago truncatula available in the United States Department of Agriculture Agricultural Research Service (USDA-ARS) and establish a core collection that would represent the existing diversity in the collection. Using 37 simple sequence repeat (SSR) markers evenly distributed across linkage groups and three derived from chloroplast sequences, 402 alleles were detected in the 297 accessions evaluated, with an average of ten alleles per locus. Unweighted pair-group method (UPGMA) analysis differentiated the accessions into four clusters. The entries collected in North Africa were highly conserved within their geographic origin, while the ones from Europe and the Mediterranean region were more diverse. A set of nested core collections was generated based on SSR data which successfully captured the existing molecular diversity as well as the morphological diversity present in the collection. A core collection with 16 accessions captured 89% of all alleles. All of the alleles were captured when the size of the core collection was increased to 64. Model-based clustering method identified two main subpopulations, one of which consisted mostly of accessions from Morocco, while the others were assigned to a second group. Overall, we have elucidated the genetic distance among the M. truncatula accessions in the USDA collection, and established a core collection which can be used by breeders and researchers to more efficiently exploit the existing natural genetic variation in M. truncatula.