In this paper we introduce and study a nonlinear generalization of discrete-time random walks on complex networks. While typical random walks are defined by static transition probabilities between network neighbors, we consider a more complicated system for modeling movement through a network where transition probabilities change in response to the current state of the system. Specifically, random walkers may be diverted preferentially towards nodes that currently have relatively more or fewer random walkers. In the weakly nonlinear regime of the dynamics we prove the existence and uniqueness of a stable stationary state fixed point corresponds to the stationary distribution of a typical (linear) random walk. We also present an asymptotic analysis that allows us to approximate the stationary state fixed point in the weakly nonlinear regime. We then turn our attention to the strongly nonlinear regime. For negative bias we characterize a period-doubling bifurcation where the stationary state fixed point loses stability and gives rise to a periodic orbit below a critical value. For positive bias we investigate the emergence of multistability of several stable stationary state fixed points. Finally, as the introduction of the nonlinear random walk on a network opens a new direction for dynamical systems and complex network theory, we discuss some important questions to address in future research.