In this paper, we describe a scalable and portable parallelized implementation of a MPEG decoder using a streaming computation paradigm, tailored to new generations of multi-core systems. A novel, hybrid approach towards parallelization of both new and legacy applications is described, where only data-intensive and performance-critical parts are implemented in the streaming domain. An architecture-independent StreamIt language is used for design, optimization and implementation of parallelized segments, while the developed StreamGate interface provides a communication mechanism between the implementation domains. The proposed hybrid approach was employed in re-factoring of a reference MPEG video decoder implementation; identifying the most performance-critical segments and re-implementing them in StreamIt language, with StreamGate interface as a communication mechanism between the host and streaming kernel. We evaluated the scalability of the decoder with respect to the number of cores, video frame formats, sizes and decomposition. Decoder performance was examined in the presence of different processor load configurations and with respect to the number of simultaneously processed frames.