Oryza coarctata, a halophyte and wild relative of rice, is grown normally in saline water. MicroRNAs (miRNAs) are non-coding RNAs that play pivotal roles in every domain of life including stress response. There are very few reports on the discovery of salt-responsive miRNAs from halophytes. In this study, two small RNA libraries, one each from the control and salt-treated (450 mM NaCl for 24 h) leaves of O. coarctata were sequenced, which yielded 338 known and 95 novel miRNAs. Additionally, we used publicly available transcriptomics data of O. coarctata which led to the discovery of additional 48 conserved miRNAs along with their pre-miRNA sequences through in silico analysis. In total, 36 known and 7 novel miRNAs were up-regulated whereas, 12 known and 7 novel miRNAs were down-regulated under salinity stress. Further, 233 and 154 target genes were predicted for 48 known and 14 novel differentially regulated miRNAs respectively. These targets with the help of gene ontology analysis were found to be involved in several important biological processes that could be involved in salinity tolerance. Relative expression trends of majority of the miRNAs as detected by real time-PCR as well as predicted by Illumina sequencing were found to be coherent. Additionally, expression of most of the target genes was negatively correlated with their corresponding miRNAs. Thus, the present study provides an account of miRNA-target networking that is involved in salinity adaption of O. coarctata.