A new variable structure control algorithm based on sliding mode prediction for a class of discrete-time nonlinear systems is presented. By employing a special model to predict future sliding mode value, and combining feedback correction and receding horizon optimization methods which are extensively applied on predictive control strategy, a discrete-time variable structure control law is constructed. The closed-loop systems are proved to have robustness to uncertainties with unspecified boundaries. Numerical simulation and pendulum experiment results illustrate that the closed-loop systems possess desired performance, such as strong robustness, fast convergence and chattering elimination.