In this paper we introduce and analyze an iteratively re-weighted algorithm, that allows to approximate the weak solution of the p-Poisson problem for 1<p2 by iteratively solving a sequence of linear elliptic problems. The algorithm can be interpreted as a relaxed Kaanov iteration, as so-called in the specific literature of the numerical solution of quasi-linear equations. The main contribution of the paper is proving that the algorithm converges at least with an algebraic rate.