A method and an apparatus for performing multi-threaded video decoding are disclosed. The method takes use of a multi-threaded scheme to process an encoded picture stream on a picture by picture basis. In the method, multiple threads are used for performing video decoding at the same time, such as one thread for the operation of parsing input bits into syntax elements of one picture implemented by the first thread, another thread for the operation of decoding the parsed syntax elements of another picture into pixel values implemented by the second thread, and the other threads for the operations of the non-reference picture, such as bidirectional predictive picture, including parsing input bits into syntax elements and the subsequent operation of decoding the parsed syntax elements into pixel values. Therefore, the decoding speed is substantially increased, and the decoding efficiency is enhanced.