Mobile gait analysis using wearable inertial measurement units (IMUs) provides valuable insights for the assessment of movement impairments in different neurological and musculoskeletal diseases, for example Parkinson's disease (PD). The increase in data volume due to arising long-term monitoring requires valid, robust and efficient analysis pipelines. In many studies an upstream detection of gait is therefore applied. However, current methods do not provide a robust way to successfully reject non-gait signals. Therefore, we developed a novel algorithm for the detection of gait from continuous inertial data of sensors worn at the feet. The algorithm is focused not only on a high sensitivity but also a high specificity for gait. Sliding windows of IMU signals recorded from the feet of PD patients were processed in the frequency domain. Gait was detected if the frequency spectrum contained specific patterns of harmonic frequencies. The approach was trained and evaluated on 150 clinical measurements containing standardized gait and cyclic movement tests. The detection reached a sensitivity of 0.98 and a specificity of 0.96 for the best sensor configuration (angular rate around the medio-lateral axis). On an independent validation data set including 203 unsupervised, semi-standardized gait tests, the algorithm achieved a sensitivity of 0.97. Our algorithm for the detection of gait from continuous IMU signals works reliably and showed promising results for the application in the context of free-living and non-standardized monitoring scenarios.