Predicting video popularity is an important task involved in managing video-sharing sites. Although many previous studies have investigated this problem, a weakness common to these studies is that their predictions rely on video access data from the past. In other words, they cannot predict the popularity of newly uploaded videos. To handle this cold start problem, this study focused on building prediction models that use only the data available at the time when a video is initially uploaded. Through supervised learning methods, this study employed prediction models to predict the popularity of videos. To further improve the overall accuracy of the prediction, we used an ensemble model to integrate these classification results to obtain the most accurate prediction. The empirical evaluation indicated that the models are effective for predicting the popularity of a video and that our model can solve the cold start problem of video popularity prediction.