Rehabilitation has been proposed as a valid measure complementary to the management of Parkinson's disease (PD). However, the mechanism underlying is not clear yet. The differential expressions of exosomal messenger RNA (mRNA) and long noncoding RNAs (lncRNAs) may play a critical role in PD progression and rehabilitation. To compare the differential expressions of exosomal mRNAs and lncRNAs, patients with PD (PWPs, Hoehn and Yahr stages 1.5-2.5, n = 6) and age- and sex-matched healthy controls (HCs, n = 6) were included in this study. All PWPs received a 2-week rehabilitation treatment in the hospital, which seemingly led to improvement in both the motor and non-motor functions. A set of differentially expressed mRNAs (DEmRNAs) and differentially expressed lncRNAs (DElncRNAs) extracted from exosomes in blood samples via next-generation sequencing (NGS) was screened out. Compared to HCs, 2,337 vs. 701 mRNAs and 1,278 vs. 445 lncRNAs were significantly upregulated and significantly downregulated, respectively, in pre-rehabilitation (pre-rehab) PWPs; 2,490 vs. 629 mRNAs and 1,561 vs. 370 lncRNAs were significantly upregulated and significantly downregulated, respectively, in post-rehabilitation (post-rehab) PWPs. Compared to pre-rehab PWPs, 606 vs. 1,056 mRNAs and 593 vs. 1,136 lncRNAs were significantly upregulated and significantly downregulated, respectively, in post-rehab PWPs. Overall, 14 differentially expressed mRNAs (DEmRNAs) and 73 differentially expressed lncRNAs (DElncRNAs) were expressed in the blood exosomes of HCs, pre- and post-rehab PWPs, simultaneously. Gene Ontology (GO) and Kyoto Encyclopedia of Genes and Genomes (KEGG) pathway enrichment analyses identified 243 significantly co-expressed lncRNA-mRNA pairs. One DEmRNA of interest (ENSG00000099795, NDUFB7) and three corresponding DElncRNAs (ENST00000564683, ENST00000570408, and ENST00000628340) were positively related. Quantitative real-time polymerase chain reaction (qRT-PCR) validated that the expression levels of NDUFB7 mRNA and the 3 DElncRNAs increased significantly in pre-rehab PWPs, but decreased significantly in post-rehab PWPs compared to HCs. NDUFB7 mRNA is a marker related to mitochondrial respiration. It is reasonably believed that mitochondrial function is associated with PD rehabilitation, and the mitochondrial pathway may involve in the pathogenesis of PD.