MicroRNAs (miRNAs) play vital roles in the adaptive response of plants to various abiotic and biotic stresses. Tall fescue (Festuca arundinacea Schreb.) is a major cool-season forage and turf grass species which is severely influenced by heat stress. To unravel possible heat stress-responsive miRNAs, high-throughput sequencing was employed for heat-tolerant PI578718 and heat-sensitive PI234881 genotypes growing in presence and absence of heat stress (40°C for 36h). By searching against the miRBase database, among 1421 reference monocotyledon miRNAs, more than 850 were identified in all samples. Among these miRNAs, 1.46% and 2.29% were differentially expressed in PI234881 and PI578718 under heat stress, respectively, and most of them were down-regulated. In addition, a total of 170 novel miRNAs belonging to 145 miRNA families were identified. Furthermore, putative targets of differentially expressed miRNAs were predicted. The regulation of selected miRNAs by heat stress was revalidated through quantitative reverse transcription PCR (qRT-PCR) analysis. Most of these miRNAs shared similar expression patterns; however, some showed distinct expression patterns under heat stress, with their putative targets displaying different transcription levels. This is the first genome-wide miRNA identification in tall fescue. miRNAs specific to PI578718, or those that exhibited differential expression profiles between the two genotypes under high temperature, were probably associated with the variation in thermotolerance of tall fescue. The differentially expressed miRNAs between these two tall fescue genotypes and their putative targeted genes will provide essential information for further study on miRNAs mediating heat response and facilitate to improve turf grass breeding.