The invention generally relates to a method of providing random access for video data in which a P-frame of the video data is configured to be random accessible in addition to I-frames. More specifically, the invention relates to a method of providing random access for video data in which a P-frame is configured to be random accessible based on a random access reference frame which is provided via a separate channel such as header area of video data packets or a metadata file, whereby the random access for video data may be effectively provided with overcoming the conventional video random access technology depending on the I-frame only. The invention makes it possible to configure a P-frame random accessible simply by accompanying a random access reference frame of small datasize, whereby video compression ratio may be improved due to smaller numbers of I-frames being included in video data than conventional arts.