Background: Stress is a critical risk factor for various health issues, but an objective, non-intrusive and effective measurement approach for stress has not yet been established. Gait, the pattern of movements in human locomotion, has been proven to be a valid behavioral indicator for recognizing various mental states in a convenient manner. Research Question: This study aims to identify the severity of stress by assessing human gait recorded through an objective, non-intrusive measurement approach. Methods: One hundred and fifty-two participants with an average age of 23 years old (SD = 1.07) were recruited. The Chinese version of the Perceived Stress Scale with 10 items (PSS-10) was used to assess participants' stress levels. The participants were then required to walk naturally while being recorded with a regular camera. A total of 1320 time-domain and 1152 frequency-domain gait features were extracted from the videos. The top 40 contributing features, confirmed by dimensionality reduction, were input into models consisting of four machinelearning regression algorithms (i.e., Gaussian Process Regressor, Linear Regression, Random Forest Regressor, and Support Vector regression), to assess stress levels. Results: The models that combined time- and frequency-domain features performed best, with the lowest RMSE (4.972) and highest validation (r = 0.533). The Gaussian Process Regressor and Linear Regression outperformed the others. The greatest contribution to model performance was derived from gait features of the waist, hands, and legs. Significance: The severity of stress can be accurately detected by machine learning models using two-dimensional (2D) video-based gait data. The machine learning models used for assessing perceived stress were reliable. Waist, hand, and leg movements were found to be critical indicator in detecting stress.