The successive projection algorithm (SPA) is a widely used algorithm for nonnegative matrix factorization (NMF). It is based on the separability assumption. In hyperspectral unmixing, that is, the extraction of materials in a hyperspectral image, separability is equivalent to the pure-pixel assumption and states that for each material present in the image there exists at least one pixel composed of only this material. SPA is fast and provably robust to noise, but it not robust to outliers. Also, it is deterministic, so for a given setting it always produces the same solution. Yet, it has been shown empirically that the non-deterministic algorithm vertex component analysis (VCA), when run sufficiently many times, often produces at least one solution that is better than the solution of SPA. In this paper, we combine the best of both worlds and introduce a randomized version of SPA dubbed RandSPA, that produces potentially different results at each run. It can be run several times to keep the best solution, and it is still provably robust to noise. Experiments on the unmixing of hyperspectral images show that the best solution among several runs of RandSPA is generally better that the solution of vanilla SPA.