Data unit identification for compressed video streams is described. In one or more implementations, a compressed video stream is received at a computing device and a determination is made as to whether prior knowledge is available that relates to the compressed video stream. Responsive to the determination that prior knowledge is available that relates to the compressed video stream, the prior knowledge is employed by the computing device to perform data unit identification for the compressed video stream. In one or more implementations, SIMD instructions are utilized to perform pattern (0x00 00) search in a batch mode. Then a byte-by-byte search is performed to confirm whether the pattern, 0x00 00, found is part of a start code, 0x00 00 01, or not.