Benders decomposition has been applied significantly to tackle large-scale optimization problems with complicating variables, which, when temporarily fixed, yield problems significantly easier to solve. Still, in its standard form, Benders decomposition, also known as the L-shaped method within the stochastic optimization community, shows several shortcomings. Leveraging the view of Benders decomposition as the dual of Dantzig-Wolfe decomposition, we propose the primal Benders decomposition. This method, a paradigm shift, is based on considering a reduced pool of complicating variables and inserting dynamically promising ones. We show that this method: (i) converges theoretically to optimality, (ii) requires only optimality cuts, referred to as Primal Benders cuts, to reach the optimal solution, (iii) benefits from the integrality of the subproblem, always viewed as a hindrance, and (iv) has an accelerated version with decreasing steps, and for which the number of iterations is, at most, the size of the complicating variables pool. We report promising computational results on the deterministic and stochastic facility location problems for which the proposed method reaches strictly optimal solutions.