Grafting is an important agricultural technique widely used for improving growth, yields and tolerance of crops to abiotic and biotic stresses. As one type of endogenous, non-coding small RNAs, microRNAs (miRNAs) regulate development and responsiveness to biotic and abiotic stresses by negatively mediating expression of target genes at the post-transcriptional level. However, there have been few detailed studies to evaluate the role of miRNAs in mediation of grafting-induced physiological processes in plants. Cucumis sativus and Cucurbita moschata are important vegetables worldwide. We constructed eight small RNA libraries from leaves and roots of seedlings that were grafted in the following four ways: (1) hetero-grafting, using cucumber as scion and pumpkin as rootstock; (2) hetero-grafting, with pumpkin as scion and cucumber as rootstock; (3) auto-grafting of cucumbers and (4) auto-grafting of pumpkins. High-throughput sequencing was employed, and more than 120 million raw reads were obtained. We annotated 112 known miRNAs belonging to 40 miRNA families and identified 48 new miRNAs in the eight libraries, and the targets of these known and novel miRNAs were predicted by bioinformatics. Grafting led to changes in expression of most miRNAs and their predicted target genes, suggesting that miRNAs may play significant roles in mediating physiological processes of grafted seedlings by regulating the expression of target genes. The potential role of the grafting-responsive miRNAs in seedling growth and long-distance transport of miRNA was discussed. These results are useful for functional characterization of miRNAs in mediation of grafting-dependent physiological processes.