A system and method provide a soundtrack recommendation service for recommending one or more soundtrack for a video (i.e., a probe video). A feature extractor of the recommendation service extracts a set of content features of the probe video and generates a set of semantic features represented by a signature vector of the probe video. A video search module of the recommendation service is configured to search for a number of video candidates, each of which is semantically similar to the probe video and has an associated soundtrack. A video outlier identification module of the recommendation service identifies video candidates having an atypical use of their soundtracks and ranks the video candidates based on the typicality of their soundtrack usage. A soundtrack recommendation module selects the soundtracks of the top ranked video candidates as the soundtrack recommendations to the probe video.