The work aims to propose a digital image watermarking algorithm based on NSCT and compressive sensing (CS) according to the good computational security of CS theory, so as to solve the conflict between the robustness, imperceptibility and security of images. First, the watermark image was divided into blocks for CS to obtain the measurements. Second, the carrier image NSCT was decomposed. The low-frequency portion was encrypted through Fibonacci scrambling and divided into blocks. Third, low-frequency sub-bands of each block were subject to LU decomposition and singular value decomposition (SVD). The measurements of each watermarking block were embedded in carrier’s singular value matrix with an appropriate embedding strength. The images containing watermark were obtained after a series of inverse transformations. In the process of watermark embedding and extracting simulation experiment results, the PSNR value of the proposed algorithm reached over 40 dB. The reconstructed watermark image was remarkably similar to the original image and had strong robustness against cropping, Gaussian noise, salt and pepper noise, Gaussian low-pass filter and JPEG compression attacks etc. The proposed algorithm has good robustness and strong invisibility, and it is practically feasible.