Tensor completion (TC), aiming to recover original high-order data from its degraded observations, has recently drawn much attention in hyperspectral images (HSIs) domain. Generally, the widely used TC methods formulate the rank minimization problem with a convex trace norm penalty, which shrinks all singular values equally, and may generate a much biased solution. Besides, these TC methods assume the whole high-order data is of low-rank, which may fail to recover the detail information in high-order data with diverse and complex structures. In this paper, a novel nonlocal low-rank regularization-based TC (NLRR-TC) method is proposed for HSIs, which includes two main steps. In the first step, an initial completion result is generated by the proposed low-rank regularization-based TC (LRR-TC) model, which combines the logarithm of the determinant with the tensor trace norm. This model can more effectively approximate the tensor rank, since the logarithm function values can be adaptively tuned for each input. In the second step, the nonlocal spatial-spectral similarity is integrated into the LRR-TC model, to obtain the final completion result. Specifically, the initial completion result is first divided into groups of nonlocal similar cubes (each group forms a 3-D tensor), and then the LRR-TC is applied to each group. Since similar cubes within each group contain similar structures, each 3-D tensor should have low-rank property, and thus further improves the completion result. Experimental results demonstrate that the proposed NLRR-TC method outperforms state-of-the-art HSIs completion techniques.