In this paper we will present an adaptive WAVELET scheme to solve the generalized Stokes problem. Using divergence free WAVELETs, the problem is transformed into an equivalent matrix vector system, that leads to a positive definite system of reduced size for the velocity. This system is solved iteratively, where the application of the infinite stiffness matrix, that is sufficiently compressible, is replaced by an adaptive approximation. Finally we prove that this adaptive method has optimal computational complexity, that is it recovers an approximate solution with desired accuracy at a computational expense that stays proportional to the number of terms in a corresponding WAVELET-best N-term approximation.