Computing the gradient of stochastic Plackett-Luce (PL) ranking models for relevance and fairness metrics can be infeasible because it requires iterating over all possible permutations of items. In this paper, we introduce a novel algorithm: PL-Rank, that estimates the gradient of a PL ranking model through sampling. Unlike existing approaches, PL-Rank makes use of the specific structure of PL models and ranking metrics. Our experimental analysis shows that PL-Rank has a greater sample-efficiency and is computationally less costly than existing policy gradients, resulting in faster convergence at higher performance.