Nowadays, cloud computing platforms are becoming increasingly prevalent and readily available, providing alternative and economic services for resource-constrained clients to perform large-scale computations. This work addresses the problem of secure outsourcing of large-scale nonnegative matrix factorization (NMF) to a cloud in a way that the client can verify the correctness of the results with small overhead. The protection of the input matrix is achieved by a random permutation and scaling encryption mechanism. By exploiting the iterative nature of NMF computation, we propose a single-round verification strategy, which can be proved to be quite effective. Theoretical and experimental results are provided to show the superior performance of the proposed scheme.