Small non-coding RNAs (sRNAs) namely microRNAs (miRNAs) and trans-acting small interfering RNAs (tasi-RNAs) play a crucial role in post-transcriptional regulation of gene expression and thus the control plant development and stress responses. In order to identify drought-responsive miRNAs and tasi-RNAs in sorghum, we constructed small RNA libraries from a drought tolerant (M35-1) and susceptible (C43) sorghum genotypes grown under control and drought stress conditions, and sequenced by Illumina Genome Analyzer IIx. Ninety seven conserved and 526 novel miRNAs representing 472 unique miRNA families were identified from sorghum. Ninety-six unique miRNAs were found to be regulated by drought stress, of which 32 were up- and 49 were down-regulated (fold change ≥ 2 or ≤ -2) at least in one genotype, while the remaining 15 miRNAs showed contrasting drought-regulated expression pattern between genotypes. A maximum of 17 and 18 miRNAs was differentially regulated under drought stress condition in the sensitive and tolerant genotypes, respectively. These results suggest that genotype dependent stress responsive regulation of miRNAs may contribute, at least in part, to the differential drought tolerance of sorghum genotypes. We also identified two miR390-directed TAS3 gene homologs and the auxin response factors as tasi-RNA targets. We predicted more than 1300 unique target genes for the novel and conserved miRNAs. These target genes were predicted to be involved in different cellular, metabolic, response to stimulus, biological regulation, and developmental processes. Genome-wide identification of stress-responsive miRNAs, tasi-RNAs and their targets identified in this study will be useful in unraveling the molecular mechanisms underlying drought stress responses and genetic improvement of biomass production and stress tolerance in sorghum.