Gait variability has potential utility as a predictive measure of dysfunction in Parkinson’s disease (PD). Current understanding implicates non-dopaminergic pathways. This study investigated the explanatory characteristics of gait variability in PD on and off medication under single and dual task conditions. Fifty people with PD were assessed twice at home (on and off l-dopa) whilst walking under single and dual task conditions, and variability (coefficient of variation, CV) was calculated for stride time and double limb support (DLS) time. Hierarchical regression analysis was used to identify predictors. The first block of variables included age, gait speed, depression (Hospital Anxiety and Depression Scale) and fatigue (Multidimensional Fatigue Inventory), and the second block included motor severity (UPDRS III), executive function (Hayling and Brixton) and attention (Test of Everyday Attention). Motor severity predicted stride time variability and DLS time variability independent of l-dopa during single task gait. Dual task gait yielded a more complex picture. Depression made a unique contribution of 9.0% on medication and 5.0% off medication to stride time variability, and visual attention and younger age contributed to DLS variability on medication, explaining 3% and 2%, respectively. Motor severity predicted DLS variability off medication, explaining 74% of variance. Different characteristics explain the two measures of gait variability, pointing to different control mechanisms.