In this study, an efficient scheme for hiding data directly in partially encrypted versions of high efficiency video coding (HEVC) videos is proposed. The content owner uses stream cipher to selectively encrypt some HEVC‐CABAC bin strings in a format‐compliant manner. Then, the data hider embeds the secret message into the encrypted HEVC videos using the specific coefficient modification technique. Consequently, it can be used in third‐party computing environments (more generally, cloud computing). For security and privacy purposes, service providers cannot access the visual content of the host video. As the coefficient is only slightly modified, the quality of the decrypted video is satisfactory. The encrypted and marked bitstreams meet the requirements of format compatibility, and have the same bit rate. At the receiving end, data extraction can be performed in the encrypted domain or decrypted domain that can be adapted to different application scenarios. Several standard video sequences with different resolutions and contents have been used for experimental evaluation.