In this paper, we have developed a novel model that is named graph-regularized tensor robust principal component analysis (GTRPCA) for denoising hyperspectral images (HSIs). Incorporating spectral graph regularization into TRPCA makes the model more accurate by preserving local geometric structures embedded in a high-dimensional space. Based on tensor singular value decomposition (t-SVD), we introduce a general tensor-based altering direction method of multipliers (ADMM) algorithm which can solve the proposed model for denoising HSIs. Experiments on both the synthetic and real captured datasets have demonstrated the effectiveness of the proposed method.