This paper introduces a novel approach for efficiently approximating solutions to Stokes problems, combining the staggered cell-centered finite element method (SCCFE) with grad-div stabilization (SCCFE $-\nabla \textrm{div}$). The scheme is implementable on general meshes through the construction of a dual mesh and a triangular dual sub-mesh. The velocity is approximated by piecewise linear $(P_1)$ functions on the dual sub-mesh, and the pressure is approximated by piecewise constant $(P_0)$ functions on the dual mesh. The scheme is cell-centered in the sense that the solution can be computed using cell unknowns of the primal mesh (for the velocity) and of the dual mesh (for the pressure). Its stability is proved using the macroelement technique. The method is presented within a rigorous theoretical framework to show the $[H^1(\varOmega )]^2$ error of the velocity and the $L^2(\varOmega )$ error of the pressure. These error estimates are verified by numerical examples.