In this paper, we design and analyze a Hybrid High-Order discretization method for the steady motion of non-Newtonian, incompressible fluids in the Stokes approximation of small velocities. The proposed method has several appealing features including the support of general meshes and high-order, unconditional inf-sup stability, and orders of convergence that match those obtained for Leray-Lions scalar problems. A complete well-posedness and convergence analysis of the method is carried out under new, general assumptions on the strain rate-shear stress law, which encompass several common examples such as the power-law and Carreau-Yasuda models. Numerical examples complete the exposition.