In this paper, we propose a cover song identification algorithm using a convolutional neural network (CNN). We first train the CNN model to classify any non-/cover relationship, by feeding a cross-similarity matrix that is generated from a pair of songs as an input. Our main idea is to use the CNN output–the cover-probabilities of one song to all other candidate songs–as a new representation vector for measuring the distance between songs. Based on this, the present algorithm searches cover songs by applying several ranking methods: 1. sorting without using the representation vectors; 2. the cosine distance between the representation vectors; and 3. the correlation between the vectors. In our experiment, the proposed algorithm significantly outperformed the algorithms used in recent studies, by achieving a mean average precision (MAP) of 93.18% in a dataset consisting of 3,300 cover-pairs and 496,200 non-cover-pairs.