We address video data-hiding on the context-adaptive variable-length coding domain of the H.264/AVC standard. It is challenging to maintain a minimum variation of rate-distortion performance when hiding data in compressed videos by slightly modifying one or more transform coefficients of prediction residual data. The fluctuant variation of rate-distortion performance is especially serious in the case of hiding data in H.264/AVC compressed videos due to the thorough use of various prediction modes. Most current video data-hiding schemes concentrate on hiding messages in video intra (I)-frames to mitigate performance degradation at the expense of limited hiding capacity and applicability. Unlike most previous video data-hiding schemes, this paper considers data-hiding schemes on both I- and predicted (P)-frames of videos. We first investigate the possible ways used to suppress the significant degradation of the rate-distortion performance for hiding data in H.264/AVC videos. Based on the investigation, a hybrid video data-hiding scheme is designed to perform the classification of 4×4 residual blocks according to the characteristics of each block and to hide message data differently in each classified block in order to reduce the performance degradation caused by the data-hiding process. The block classification is based on the magnitude of the last non-zero coefficient and the coefficient difference energy of each block to select suitable blocks that are capable of contributing less degradation of coding performance for hiding additional messages. Moreover, the proposed data-hiding algorithm is incorporated with the rate-distortion optimization loop of the H.264/AVC encoder to provide further degradation suppression on the output bit-rate and decoded quality. From experiments on several well-known test videos, it can be seen that the proposed data-hiding scheme demonstrates improved efficiency on video quality and output bit-rate compared to other similar methods.