We present a Petrov-Galerkin reduced basis (RB) approximation for the parameterized Stokes equation. Our method, which relies on a reduced solution space and a parameter-dependent test space, is shown to be stable (in the sense of Babuska) and algebraically stable '(a bound on the condition number of the online system can be established). Compared to other stable RB methods that can also be shown to be algebraically stable, our approach is among those with the smallest online time cost and it has general applicability to linear non-coercive problems without assuming a saddle-point structure. (C) 2015 Academie des sciences. Published by Elsevier Masson SAS. All rights reserved.