Non-motor symptoms of Parkinson’s disease (PD) such as dysautonomia and REM sleep behavior disorder (RBD) are recognized to be important prodromal symptoms that may also indicate clinical subtypes of PD with different pathogenesis. Unbiased clustering analyses showed that subjects with dysautonomia and RBD symptoms, as well as early cognitive dysfunction, have faster progression of the disease. Through analysis of the Parkinson’s Progression Markers Initiative (PPMI) de novo PD cohort, we tested the hypothesis that symptoms of dysautonomia and RBD, which are readily assessed by standard questionnaires in an ambulatory care setting, may help to independently prognosticate disease progression. Although these two symptoms associate closely, dysautonomia symptoms predict severe progression of motor and non-motor symptoms better than RBD symptoms across the 3-year follow-up period. Autonomic system involvement has not received as much attention and may be important to consider for stratification of subjects for clinical trials and for counseling patients.