MicroRNAs are approximately 21-nt long, non-coding RNAs that play critical roles in post-transcriptional gene regulation. Even though a large number of miRNAs have been identified, annotating their functions remains a challenge. We develop a computational, transcriptome-based approach to annotating stress-inducible microRNAs in plants. With this approach, we find that nineteen microRNA genes of eleven microRNA families in Arabidopsis thaliana are up-regulated by cold stress. Our experiments validate that among the eleven microRNAs, eight are differentially induced and three are constantly expressed under low temperature. Our result expands the number of cold-inducible microRNAs from four to eight. A promoter analysis further reveals that the cold-responsive microRNA genes contain many known stress-related cis-regulatory elements in their promoters. Our analysis also indicates that many signaling pathways, such as auxin pathways, may be affected by cold-inducible microRNAs. Our approach can be applied to plant microRNAs responding to other abiotic and biotic stresses. The research demonstrates that machine learning methods, augmented by wet-lab analysis, hold a great promise for functional annotation of microRNAs.