MicroRNAs (miRNAs) are involved in plant growth, development, and response to biotic and abiotic stresses. Most of the miRNAs that have been identified in model plants are well characterized, but till now, no reports have previously been published concerning miRNAs in Paulownia australis. In order to investigate miRNA-guided transcript target regulation in P. australis, small RNA libraries from two P. australis (diploids, PA2; and autotetraploids, PA4) genotypes were subjected to Solexa sequencing. As a result, 10,691,271 (PA2) and 10,712,733 (PA4) clean reads were obtained, and 45 conserved miRNAs belonging to 15 families, and 31 potential novel miRNAs candidates were identified. Compared with their expression levels in the PA2 plants, 26 miRNAs were up-regulated and 15 miRNAs were down-regulated in the PA4 plants. The relative expressions of 12 miRNAs were validated by quantitative real-time polymerase chain reaction. Using the degradome approach, 53 transcript targets were identified and annotated based on Gene Ontology and Kyoto Encyclopedia of Genes and Genomes pathway analysis. These targets were associated with development, stimulus response, metabolism, signaling transduction and biological regulation. Among them, 11 targets, including TCP transcription factors, auxin response factors, squamosa promoter-binding-like proteins, scarecrow-like proteins, L-type lectin-domain containing receptor kinases and zinc finger CCCH domain-containing protein, cleaved by four known miRNA family and two potentially novel miRNAs were found to be involved in regulating plant development, biotic and abiotic stresses. The findings will be helpful to facilitate studies on the functions of miRNAs and their transcript targets in Paulownia.