A novel reversible data hiding algorithm for H.264/AVC videos is proposed. Histogram Shifting (HS) of motion vector values is used efficiently in reversible data hiding to embed data. By designating a specific decoded reference frame, the distortion accumulation effects due to modification of the motion vectors is overcome. All the extracted information can be recovered without loss of the original compressed video carrier. The experimental results show that the proposed algorithm is simple, has higher capacity and invisibility than other existing schemes, and can adjust the relationship between capacity and invisibility according to embedded load.