While depression is one of the most common mental disorders affecting more than 300 million people across the world, it is often left undiagnosed. This paper investigated the association between depression and gait characteristics with the aim to assist in diagnosing depression. Our dataset consisted of 121 healthy people and 126 patients with depression who diagnosed by psychiatrists according to the Diagnostic and Statistical Manual of Mental Disorders. Spatiotemporal, temporal-domain, and frequency-domain features were extracted based on the walking data of 247 participants recorded by Microsoft Kinect (Version 2). Multiple logistic regression was used to analyze the variance of spatiotemporal (12.55%), time-domain (58.36%), and frequency-domain features (60.71%) on recognizing depression based on Nagelkerke's R-2 measure, respectively. The contributions of the different types of features were further explored by building machine learning models by using support vector machine algorithm. All the combinations of the three types of gait features were used as training data of machine learning models, respectively. The results showed that the model trained using only time- and frequency-domain features demonstrated the same best performance compared to the model trained using all the features (sensitivity = 0.94, specificity = 0.91, and AUC = 0.93). These results indicated that depression could be effectively recognized through gait analysis. This approach is a step forward toward developing low-cost, non-intrusive solutions for real-time depression recognition.