In this paper we propose and analyze a new augmented mixed finite element method for the Navier-Stokes problem. Our approach is based on the introduction of a “nonlinear-pseudostress” tensor linking the pseudostress tensor with the convective term, which leads to a mixed formulation with the nonlinear-pseudostress tensor and the velocity as the main unknowns of the system. Further variables of interest, such as the fluid pressure, the fluid vorticity and the fluid velocity gradient, can be easily approximated as a simple postprocess of the finite element solutions with the same rate of convergence. The resulting mixed formulation is augmented by introducing Galerkin least-squares type terms arising from the constitutive and equilibrium equations of the Navier-Stokes equations and from the Dirichlet boundary condition, which are multiplied by stabilization parameters that are chosen in such a way that the resulting continuous formulation becomes well-posed. Then, the classical Banach fixed point theorem and the Lax-Milgram lemma are applied to prove well-posedness of the continuous problem. Similarly, we establish well-posedness and the corresponding Cea estimate of the associated Galerkin scheme considering any conforming finite element subspace for each unknown. In particular, the associated Galerkin scheme can be defined by employing Raviart-Thomas elements of degree K for the nonlinear-pseudostress tensor and continuous piecewise polynomial elements of degree K + 1 for the velocity, which leads to an optimal convergent scheme. In addition, we provide two iterative methods to solve the corresponding nonlinear system of equations and analyze their convergence. Finally, several numerical results illustrating the good performance of the method are provided.