Recently, an approach for the rapid detection of small oscillation faults based on deterministic leing theory was proposed for continuous-time systems. In this paper, a fault detection scheme is proposed for a class of nonlinear discrete-time systems via deterministic leing. By using a discrete-time extension of deterministic leing algorithm, the general fault functions (i.e., the intal dynamics) underlying normal and fault modes of nonlinear discrete-time systems are locally-accurately approximated by discrete-time dynamical radial basis function (RBF) networks. Then, a bank of estimators with the obtained knowledge of system dynamics embedded is constructed, and a set of residuals are obtained and used to measure the differences between the dynamics of the monitored system and the dynamics of the trained systems. A fault detection decision scheme is presented according to the smallest residual principle, i.e., the occurrence of a fault can be detected in a discrete-time setting by comparing the magnitude of residuals. The fault detectability analysis is carried out and the upper bound of detection time is derived. A simulation example is given to illustrate the effectiveness of the proposed scheme.