Learning PieceWise Affine Output-Error (PWA-OE) models from data requires to estimate a finite set of affine output-error sub-models as well as a partition of the regressors space over which the sub-models are defined. For an output-error type noise structure, the algorithms based on ordinary least squares (LS) fail to compute a consistent estimate of the sub-model parameters. On the other hand, the prediction error methods (PEMs) provide a consistent parameter estimate, however, they require to solve a non-convex optimization problem for which the numerical algorithms may get trapped in a local minimum, leading to inaccurate estimates. In this letter, we propose a recursive bias-correction scheme for identifying PWA-OE models, retaining the computational efficiency of the standard LS algorithms while providing a consistent estimate of the sub-model parameters, under suitable assumptions. The proposed approach allows one to recursively update the estimates of the sub-models parameters and to cluster the regressors. Linear multi-category techniques are then employed to estimate a partition of the regressor space based on the estimated clusters. The performance of the proposed algorithm is demonstrated via an academic example.