Heart rate and respiration display fluctuations that are interlinked by central regulatory mechanisms of the autonomic nervous system (ANS). Joint assessment of respiratory time series along with heart rate variability (HRV) may therefore provide information on ANS dysfunction. The aim of this study was to investigate cardio-respiratory interaction in patients with Parkinson\'s disease (PD), a neurodegenerative disorder that is associated with progressive ANS dysfunction. Short-term ECG and respiration were recorded in 25 PD patients and 28 healthy controls during rest. To assess ANS dysfunction we analyzed joint symbolic dynamics of heart rate and respiration, cardio-respiratory synchrograms along with heart rate variability. Neither HRV nor cardio-respiratory synchrograms were significantly altered in PD patients. Symbolic analysis, however, identified a significant reduction in cardio-respiratory interactions in PD patients compared to healthy controls (16 +/- 3.6 % vs. 20 +/- 6.1 %; p= 0.02). In conclusion, joint symbolic analysis of cardio-respiratory dynamics provides a powerful tool to detect early signs of autonomic nervous system dysfunction in Parkinson\'s disease patients at an early stage of the disease.