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 are represented in non-strict feedback form. The NN backstepping approach is utilized to design the adaptive output feedback controller consisting of: (1) an NN observer to estimate the system states and (2) two NNs to generate the virtual and actual control inputs, respectively. The non-causal problem encountered during the control design is overcome by using a dynamic NN which is constructed through a feedforward NN with a novel weight tuning law. The separation principle is relaxed, persistency of excitation condition (PE) is not needed and certainty equivalence principle is not used. The uniformly ultimate boundedness (UUB) of the closed-loop tracking error, the state estimation errors and the NN weight estimates is demonstrated. Though the proposed work is applicable for second order nonlinear discrete-time systems expressed in non-strict feedback form, the proposed controller design can be easily extendable to an nth order nonlinear discrete-time system.