In this work a dual-mixed approximation of a nonlinear generalized Stokes problem is studied. The problem is analyzed in Sobolev spaces which arise naturally in the problem formulation. Existence and uniqueness results are given and error estimates are derived. It is shown that both lowest-order and higher-order mixed finite elements are suitable for the approximation method. Numerical experiments that support the theoretical results are presented.