Abstract Background A class of eukaryotic non-coding RNAs termed microRNAs (miRNAs) interact with target mRNAs by sequence complementarity to regulate their expression. The low abundance of some miRNAs and their time- and tissue-specific expression patterns make experimental miRNA identification difficult. We present here a computational method for genome-wide prediction of Arabidopsis thaliana microRNAs and their target mRNAs. This method uses characteristic features of known plant miRNAs as criteria to search for miRNAs conserved between Arabidopsis and Oryza sativa . Extensive sequence complementarity between miRNAs and their target mRNAs is used to predict miRNA-regulated Arabidopsis transcripts. Results Our prediction covered 63% of known Arabidopsis miRNAs and identified 83 new miRNAs. Evidence for the expression of 25 predicted miRNAs came from northern blots, their presence in the Arabidopsis Small RNA Project database, and massively parallel signature sequencing (MPSS) data. Putative targets functionally conserved between Arabidopsis and O. sativa were identified for most newly identified miRNAs. Independent microarray data showed that the expression levels of some mRNA targets anti-correlated with the accumulation pattern of their corresponding regulatory miRNAs. The cleavage of three target mRNAs by miRNA binding was validated in 5' RACE experiments. Conclusions We identified new plant miRNAs conserved between Arabidopsis and O. sativa and report a wide range of transcripts as potential miRNA targets. Because MPSS data are generated from polyadenylated RNA molecules, our results suggest that at least some miRNA precursors are polyadenylated at certain stages. The broad range of putative miRNA targets indicates that miRNAs participate in the regulation of a variety of biological processes.