Since the small RNA-sequencing (sRNA-seq) technology became available, it allowed the discovery of thousands new microRNAs (miRNAs) in humans and many other species, providing new data on these small RNAs (sRNAs) of high biological and translational relevance. MiRNA discovery has not yet reached saturation, even in the most studied model organisms, and many researchers are using sRNA-seq in studies with different aims in biomedicine, fundamental research and in applied animal sciences. We review several miRNA discovery and characterization software tools that implement different strategies, providing a useful guide for researchers to select the programs best suiting their study objectives and data. After a brief introduction on miRNA biogenesis, function and characteristics, useful to understand the biological background considered by the algorithms, we survey the current state of miRNA discovery bioinformatics discussing 26 different sRNA-seq-based miRNA prediction software and toolkits released in the past 6 years, including 15 methods specific for miRNA prediction and 11 more general-purpose software suites for sRNA-seq data analysis. We highlight the main features of mature miRNAs and miRNA precursors considered by the methods categorizing them according to prediction strategy and implementation. In addition, we describe a typical miRNA prediction and analysis workflow by delineating the objectives, potentialities and main steps of sRNA-seq data analysis projects, from preparatory data processing to miRNA prediction, quantification and diverse downstream analyses. Finally, we outline the caveats affecting sRNA-seq-based prediction tools, and we indicate the possibilities offered by data set pooling and by integration with other types of high-throughput sequencing data.