A video encoding device includes a coded data transcoding section 131 for transcoding first coded data generated by a first video encoding section 11 to generate second coded data, wherein the coded data transcoding section 131 includes: a prediction mode adding section 1312 for generating intra prediction modes unusable by the first video encoding section 11 and usable by a second video encoding section 14; and a prediction mode selecting section 1313 for evaluating the prediction modes generated by the prediction mode adding section 1312 and, based on the evaluation results, selecting a prediction mode used by the second video encoding section 14.