In plants, microRNAs (miRNAs) comprise one of three classes of small RNAs regulating gene expression at the post-transcriptional level. Many plant miRNAs are conserved, and play a role in development, abiotic stress responses or pathogen responses. However, some miRNAs have only been found in certain species. Here, we use deep-sequencing, computational and molecular methods to identify, profile, and describe conserved and non-conserved miRNAs in four grapevine (Vitis vinifera) tissues. A total of 24 conserved miRNA families were identified in all four tissues, and 26 known but non-conserved miRNAs were also found. In addition to known miRNAs, we also found 21 new grapevine-specific miRNAs together with their star strands. We have also shown that almost all of them originated from single genes. Furthermore, 21 other plausible miRNA candidates have been described. We have found that many known and new miRNAs showed tissue-specific expression. Finally, 112 target mRNAs of known and 44 target mRNAs of new grapevine-specific miRNAs were identified by genomic-scale high-throughput sequencing of miRNA cleaved mRNAs.