Based on concurrent exploration of both algorithm and architecture, this paper introduces an efficient verification methodology that targets at comprehensive functional verification throughout different levels of design granularities for multi-format media SoC's with applications in MPEG's Reconfigurable Video Coding. We present a verification technique that minimizes the number of test patterns but at the same time covering multiple profiles based on the functional commonalities extracted from multiple coding standards. In addition, algorithmic complexity analysis and dataflow modeling are also used to gain insight into flexible video architecture at early design stage in facilitating more efficient verification environment. Furthermore, an isolation technique is also presented for independent verification of coarse grain modules in the system level. We have shown that this verification methodology can effectively enhance the reliability and efficiency of SoC's with high complexity and reconfigurability.