Long noncoding RNA (lncRNA), circular RNA (circRNA), and microRNA (miRNA) are important in the regulation of life activities. However, their function is unclear in Paulownia fortunei. To identify lncRNAs, circRNAs, and miRNA, and investigate their roles in the infection progress of Paulownia witches’ broom (PaWB) disease, we performed RNA sequencing of healthy and infected P. fortunei. A total of 3126 lncRNAs, 1634 circRNAs, and 550 miRNAs were identified. Among them, 229 lncRNAs, 65 circRNAs, and 65 miRNAs were differentially expressed in a significant manner. We constructed a competing endogenous RNA (ceRNA) network, which contains 5 miRNAs, 4 circRNAs, 5 lncRNAs, and 15 mRNAs, all of which were differentially expressed between healthy and infected P. fortunei. This study provides the first catalog of candidate ceRNAs in Paulownia and gives a revealing insight into the molecular mechanism responsible for PaWB.