Recently proposed steganalysis methods based on the local optimality of motion vector prediction (MVP) indicate that the existing HEVC (high efficiency video coding) motion vector (MV) domain video steganography algorithms can disturb the optimality of MVP in advanced motion vector prediction (AMVP) technology. In order to improve the security of steganography algorithm, this paper proposes an MV domain steganography method in HEVC based on MVP’s index and motion vector difference (MVD). First, we analyze the conditions that need to be met for steganography to resist attacks from MVP’s optimality features and other traditional steganalysis features. Then, a distortion function for minimizing embedding distortion is designed, and an algorithm for secret message embedding and extraction in units of inter-frame is proposed. Experimental results show that the proposed algorithm can resist attacks based on the optimality of MVP and also has high security against other traditional steganalysis methods. In addition, the proposed algorithm has excellent performance in visual quality and coding efficiency, and can be applied to practical scenarios of video covert communication.