Watermarking technology based on high-efficiency video coding (HEVC) is evolving such that it can be used in various scenarios, such as copyright protection, ownership certification, tamper detection, and authentication. However, video watermarking algorithms based on HEVC still have poor resistance to recompression attack, which seriously affects the practicability of watermarking algorithms. To solve this limitation, we propose a robust HEVC watermarking algorithm based on the analysis of the characteristics of HEVC recompression. The influencing factors of choosing embedding carrier are discussed, and the calculation formula of texture complexity is then deduced. According to the texture complexity, the watermark is embedded into the stable 4 × 4 luma blocks. Specifically, the watermark information is completely embedded after modulating the signs of the quantized discrete sinusoidal transform coefficients of the carrier. Experimental results show that the algorithm is robust to the recompression attack with constant quantization parameter. There is no obvious artifact after watermark embedding, which reflects the proposed algorithm has good imperceptibility. In addition, the embedding and extraction process of the algorithm is simple and fast, and the embedding of the watermark does not increase the video bit rate.