Preconditioned GMRES is a powerful iterative method for linear systems. In this talk, I will show how the concept of preconditioned GMRES can be extended to the general class of nonlinear optimization problems, using genuinely nonlinear preconditioners. I will present a nonlinear GMRES (N-GMRES) optimization method, which combines preliminary iterates generated by a stand-alone simple optimization method (the nonlinear preconditioner) to produce accelerated iterates in a generalized Krylov space. The nonlinear acceleration process, which is closely related to existing acceleration methods for nonlinear systems that include so-called Anderson acceleration, is combined with a line search in every step to obtain a general nonlinear optimization method for which global convergence can be proved when steepest-descent preconditioning is used. Numerical tests show that N-GMRES is competitive with established nonlinear optimization methods, and outperforms them for a difficult canonical tensor approximation problem when an advanced nonlinear preconditioner is used. This suggests that the real power of N-GMRES may lie in its ability to use powerful problem-dependent nonlinear preconditioners. Extension of these ideas to nonlinear preconditioning for the nonlinear CG optimization method is also discussed, and results are presented showing the effectiveness of the approach.