miRDeepFinder is a software package developed to identify and functionally analyze plant microRNAs (miRNAs) and their targets from small RNA datasets obtained from deep sequencing. The functions available in miRDeepFinder include pre-processing of raw data, identifying conserved miRNAs, mining and classifying novel miRNAs, miRNA expression profiling, predicting miRNA targets, and gene pathway and gene network analysis involving miRNAs. The fundamental design of miRDeepFinder is based on miRNA biogenesis, miRNA-mediated gene regulation and target recognition, such as perfect or near perfect hairpin structures, different read abundances of miRNA and miRNA*, and targeting patterns of plant miRNAs. To test the accuracy and robustness of miRDeepFinder, we analyzed a small RNA deep sequencing dataset of Arabidopsis thaliana published in the GEO database of NCBI. Our test retrieved 128 of 131 (97.7%) known miRNAs that have a more than 3 read count in Arabidopsis. Because many known miRNAs are not associated with miRNA*s in small RNA datasets, miRDeepFinder was also designed to recover miRNA candidates without the presence of miRNA*. To mine as many miRNAs as possible, miRDeepFinder allows users to compare mature miRNAs and their miRNA*s with other small RNA datasets from the same species. Cleaveland software package was also incorporated into miRDeepFinder for miRNA target identification using degradome sequencing analysis. Using this new computational tool, we identified 13 novel miRNA candidates with miRNA*s from Arabidopsis and validated 12 of them experimentally. Interestingly, of the 12 verified novel miRNAs, a miRNA named AC1 spans the exons of two genes (UTG71C4 and UGT71C3). Both the mature AC1 miRNA and its miRNA* were also found in four other small RNA datasets. We also developed a tool, "miRNA primer designer" to design primers for any type of miRNAs. miRDeepFinder provides a powerful tool for analyzing small RNA datasets from all species, with or without the availability of genome information. miRDeepFinder and miRNA primer designer are freely available at http://www.leonxie.com/DeepFinder.php and at http://www.leonxie.com/miRNAprimerDesigner.php , respectively. A program (called RefFinder: http://www.leonxie.com/referencegene.php ) was also developed for assessing the reliable reference genes for gene expression analysis, including miRNAs.