—This letter studies the impact of relay selection (RS) on the performance of cooperative non-orthogonal multiple access (NOMA). In particular, a two-stage RS strategy is proposed, and analytical results are developed to demonstrate that this two-stage strategy can achieve the minimal outage probability among all possible RS schemes, and realize the maximal diversity gain. The provided simulation results show that cooperativ e NOMA with this two-stage RS scheme outperforms that with the conventional max-min approach, and can also yield a significant performance gain over orthogonal multiple access.