An information hiding algorithm with prediction mode modulating for H.264/AVC is proposed. According to the luminance values of the reference pixels, the luminance blocks for information embedding are selected. The information is embedded by modulating the prediction modes of 4×4 luminance blocks. If the best mode does not match the information bit, the prediction modes can be modulated by replacing the best mode with the substitute mode. The substitute mode is the one with the least Lagrangian cost among those having different parity with the best mode. The extraction of information can be performed directly from the encoded stream without resorting to the original video, and merely requires decoding the intra prediction mode from bit stream rather than decoding the whole video. Experimental results show that the proposed hiding scheme can effectively embed information with little bit rate increase and almost no quality degradation.