Cloud service has been emerging as a promising alternative to handle massive volumes of video sequences triggered by increasing demands on video service, especially surveillance and entertainment. Lossless compression of encoded video bitstreams can further eliminate the redundancies without altering the contents and facilitate the efficiency of cloud storage. In this paper, we propose a novel lossless compression scheme to further compress the video bitstreams generated by the state-of-the-art hybrid coding frameworks like H.264/AVC and HEVC. Different from transcoding, the proposed scheme develops frequency prediction and Macro Block (MB) merging to eliminate the redundancies remained in the intra- and inter-predicted frames with a strict guarantee of video fidelity. To our best knowledge, this paper is the first attempt to realize lossless compression of video bitstreams generated by advanced coding standards H.264/AVC and HEVC. Experimental results demonstrate that the proposed scheme can achieve compression gains of 17.38% and 10.85% on standard test sequences and surveillance videos, respectively.