Gait phase recognition plays a key role in the motion control of exoskeleton robots. Surface electromyography (sEMG) is predictive and contributes to accurate gait phase recognition. To address the challenge of low accuracy of intention recognition in exoskeleton robots, a hybrid algorithm using an improved cuckoo-search-based support vector machine (ICS-SVM) was proposed to achieve accurate gait phase recognition. First, the raw sEMG signals from ten subjects were collected through gait experiments. Second, time-domain features including mean absolute value, waveform length, variance, and root mean square were extracted from the sEMG signals. Third, the support vector machine (SVM) used in this study is the most common model for intention recognition. However, the SVM has the problem of being sensitive to parameter tuning. A cuckoo search (CS) algorithm was applied to optimize the penalty factor and kernel function parameter of the SVM to accelerate convergence. An information-sharing mechanism, a local enhancement operator, and a new way to build a bird’s nest are introduced to overcome the low search efficiency of the original algorithm and its tendency to fall into local optimal solutions. Experiments showed that the algorithm model combines the advantages of the ICS algorithm and the SVM model, and can accurately distinguish seven gait phases, with an average recognition accuracy of 95.125%, which is higher than those of the SVM (92.177%) and CS-based SVM (CS-SVM) (94.170%) models. This study will provide technical support for the development of intelligent medical and exoskeleton robotics fields.