A system and method are provided for discovering new friends using recommendation paths in a media recommendation network. In general, media items are recommended among users in a media recommendation network. Use of media items by the users is monitored. If the use of a media item by a user exceeds a threshold, a determination is made as to whether the media item was recommended to the user. If so, that recommendation is identified as a highly valued recommendation for that user. Thereafter, when the user desires to identify new friends from which to receive recommendations and to which to send recommendations, a recommendation path for the highly valued recommendation is identified. Users in the recommendation path that are not already friends of the user are identified as potential new friends for the user.