The nonlocal-based model for hyperspectral image (HSI) denoising first uses nonlocal self-similarity (NSS) prior to group similar full-band patches into 3-D nonlocal full-band groups (tensors) using a block matching (BM) operation, and then a low-rank (LR) penalty is typically applied to each nonlocal full-band group to reduce noise. While nonlocal-based methods have shown promising performance in HSI denoising, most existing methods have only considered the LR property of the nonlocal full-band group while ignoring the strong correlation between sparse coefficients. Moreover, such methods often result in unsatisfactory visual artifacts due to the noise sensitivity of BM operations, while requiring expensive computations. To address these limitations, this article proposes a novel nonlocal structured sparsity regularization (NLSSR) approach for HSI denoising. First, to mitigate the noise sensitivity of the BM operation, we propose a graph-based domain distance scheme to index similar full-band patches to form the nonlocal full-band group. Second, we design an adaptive unidirectional LR dictionary with low complexity that takes into account the differences in intrinsic structure correlation among different modes of the nonlocal full-band tensor. Third, we utilize a global spectral LR prior to reduce spectral redundancy. Fourth, we develop a generalized soft-thresholding (GST) algorithm based on the alternating minimization framework to solve the NLSSR-based HSI denoising problem. We perform extensive experiments on both simulated and real data to show that the proposed NLSSR algorithm outperforms many popular or state-of-the-art HSI denoising methods in both quantitative and visual evaluations.