Elymus nutans and Elymus sibiricus are two important perennial forage grasses of the genus Elymus, widely distributed in high altitude regions of Western and Northern China, especially on the Qinghai-Tibetan Plateau. Information on phenotypic and genetic diversity is limited, but necessary for Elymus germplasm collection, conservation, and utilization. In the present study, the phenotypic and genetic differentiation of 73 accessions of the two species were evaluated using 15 phenotypic traits and 40 expressed sequence tag derived simple sequence repeat markers (EST-SSRs). The results showed that only 7.23% phenotypic differentiation (Pst) existed between the two Elymus species based on fifteen quantitative traits. Principal component analysis (PCA) revealed that leaf traits, spike traits, and some seed traits were dominant factors in phenotypic variation. Moreover, 396 (97.8%) and 331 (87.1%) polymorphic bands were generated from 40 EST-SSR primers, suggesting high levels of genetic diversity for the two species. The highest genetic diversity was found in the Northeastern Qinghai-Tibetan Plateau groups. Clustering analysis based on molecular data showed that most accessions of each Elymus species tended to group together. Similar results were described by principal coordinates analysis (PCoA) and structure analysis. The molecular variance analysis (AMOVA) revealed that 81.47% and 89.32% variation existed within the geographical groups for the two species, respectively. Pearson’s correlation analyses showed a strong positive correlation between Nei’s genetic diversity and annual mean temperature. These results could facilitate Elymus germplasm collection, conservation, and future breeding.