microRNAs (miRNAs) are endogenous non-coding RNAs of ~21 nucleotides in length discovered in recent years. They are involved in diverse pathways and play an important role in gene regulation in plants and animals. There are two main groups of approaches to miRNA discovery, which are cDNA cloning and computational identification. Since some miRNAs are expressed at a low level and the expression of many miRNAs has spatio-temporal specificity, it is difficult to find them through cDNA cloning. However, computational approaches can predict the miRNAs specifically expressed or with low abundance, which is complement to cDNA cloning. Computational approaches have hence gained wide attention. In this review, the computational approaches to miRNA discovery were summarized. According to their intrinsic characteristics, computational approaches were categorized into five classes: (1) homology search; (2) prediction based on comparative genomics; (3) scoring candidates using the sequence and structure characteristics; (4) prediction combined with targets; and (5) prediction with machine learning. The principles of each class of the approaches and their advantages and limitations in miRNA discovery were discussed. Finally, the future direction in miRNA discovery was pointed out.