We introduce coined Nonlinear Quantum Walks (NLQW) on the lattice. The NLQW is based on the walker acquisition of non-linear (probability dependent) phases at each step of the walk. The most striking result is the formation of non-dispersive pulses in the probability distribution (soliton-like structures). These exhibit a variety of dynamical behaviors, including ballistic motion, dynamical localization, non-elastic collisions and chaotic behavior, in the sense that the dynamics is very sensitive to the nonlinearity strength.