Mitochondrial disorders are multisystem conditions that can potentially affect gait in many ways. The aim of this study was to select the optimal protocol to quantify the spatiotemporal parameters of gait in ambulatory children with mitochondrial disorders based on feasibility, test-retest reliability, and the difference between patients and controls. Gait at self-selected pace was quantified in ambulatory children with a genetically confirmed primary mitochondrial disease using the GAITRite electronic walkway. Three protocols were tested: pre-exercise, post-exercise (after a 3-min walking test), and recovery. In 14 ambulatory patients, we showed good to perfect reliability for velocity, cadence, step length, step time, step time variability, and step width in the recovery condition. The difference between patients and 70 individually age- and gender matched healthy controls only became apparent in the post-exercise protocol. In conclusion, measuring spatiotemporal parameters of gait using the GAITRite in ambulatory children with mitochondrial disease is feasible and reliable for most of the parameters measured. When using gait analysis in future studies in children with mitochondrial disease, we advise i) to use an exercise test prior to the gait analysis, ii) to let children practice the test before the actual data collection, and iii) not to use symmetry parameters.