A media decoding method based on cloud computing and decoder thereof are provided by embodiments of the present invention, which are easy to use and applicable to a media of any form, and its requirement for computer resource is low. The method includes: extracting representing features from a media code stream to be decoded; searching in the cloud for a media object which has similar representing features with the media code stream to be decoded by using a feature matching method and the representing features extracted; filling, replacing and improving parts or segments of the media code stream to be decoded with whole or parts of the media object.