With the advent of web 2.0, billions of videos are now freely available online. Meanwhile, rich user generated information for these videos such as tags and online encyclopedia offer us a chance to enhance the existing video analysis technologies. In this paper, we propose a mash-up framework to realize video category recommendation by leveraging web information from different sources. Under this framework, we build a web video dataset from the YouTube API, and construct a concept collection for web video category recommendation (CCWV-CR) from this dataset, which consists of the web video concepts with small semantic gap and high categorization distinguishability. Besides, Wikipedia Propagation is proposed to optimize the video similarity measurement. The experiments on the large-scale dataset with 80,031 web videos demonstrate that: (1) the mash-up category recommendation framework has a great improvement than the existing state-of-art methods. (2) CCWV-CR is an efficient feature space for video category recommendation. (3) Wikipedia Propagation could boost the performance of video category recommendation.