An adaptive neural network (NN)-based output feedback controller is proposed to deliver a desired tracking performance for a class of discrete-time nonlinear systems, which is represented in non-strict feedback form. The NN backstepping approach is utilized to design the adaptive output feedback controller consisting of: 1) a NN observer to estimate the system states with the input-output data, and 2) two NNs to generate the virtual and actual control inputs, respectively. The non-causal problem in the discrete-time backstepping design is avoided by using the universal NN approximator. The persistence excitation (PE) condition is relaxed both in the NN observer and NN controller design. The uniformly ultimate boundedness (UUB) of the closed-loop tracking error, the state estimation errors and the NN weight estimates is shown.