In this paper we introduce and analyze a virtual element method (VEM) for a mixed variational formulation of the Stokes problem in which the pseudostress and the velocity are the only unknowns, whereas the pressure is computed via a postprocessing formula. We first recall the corresponding continuous variational formulation, and then, following the basic principles for mixed-VEM, define the virtual finite element subspaces to be employed, introduce the associated interpolation operators, and provide the respective approximation properties. In particular, the latter includes the estimation of the interpolation error for the pseudostress variable measured in the H(div)-norm. We remark that a Bramble-Hilbert type theorem for averaged Taylor polynomials plays a key role in the respective analysis. Next, and in order to define calculable discrete bilinear forms, we propose a new local projector onto a suitable space of polynomials, which takes into account the main features of the continuous solution and allows the explicit integration of the terms involving the deviatoric tensors. The uniform boundedness of the resulting family of local projectors is established and, using the aforementioned compactness theorem, its approximation properties are also derived. In addition, we show that the global discrete bilinear forms satisfy all the hypotheses required by the Babu. ska-Brezzi theory. In this way, we conclude the well-posedness of the actual Galerkin scheme and derive the associated a priori error estimates for the virtual solution as well as for the fully computable projection of it. Finally, several numerical results illustrating the good performance of the method and confirming the theoretical rates of convergence are presented.