The problem of tracking control for a class of uncertain non-affine discrete-time nonlinear systems with internal dynamics is addressed. The fixed point theorem is first employed to ensure the control problem in question is solvable and well-defined. Based on it, an adaptive output feedback control scheme based on neural network (NN) is presented. The proposed control algorithm consists of two parts: a dynamic compensator is introduced to stabilise the linear portion of the tracking error system; a single-hidden-layer neural network (SHL NN) approximation mechanism is introduced to cancel the uncertainties resulting from the non-affine function, where the recursive weight update rules of NN estimation are derived from the discrete-time version of Lyapunov control theory. Ultimate boundedness of the error signals is shown through Lyapunov's direct method and the discrete-time version of input-to-state stability (ISS) theory. Finally, a model of automatical underwater vehicle (AUV) is considered to show the effectiveness of the proposed control scheme.