Mobile Jukebox is a service offered by mobile operators to their clients, such that subscribers can buy or download anywhere, anytime full-length music tracks over the 3G Mobile networks. Unlike some music download services, the subscribers can reuse the selected tracks on their music players or computers. As the amount of online music grows rapidly, Jukebox providers employ automatic recommender service as an important tool for music listeners to find music that they will appreciate. On one hand, Jukebox recommender service recommend music based on users’ musical tastes and listening habits which reduces the browsing time for searching new songs and album releases. On the other hand, users care about the privacy of their preferences and individuals’ behaviors regarding the usage of recommender service. This work presents our efforts to design an agent based middle-ware that enables the end-user to use Jukebox recommender services without revealing his sensitive profile information to that service or any third party involved in this process. Our solution relies on a distributed multi-agent architecture involving local agents running on the end-user mobile phone and two stage obfuscation process used to conceal the local profiles of end-users with similar preferences. The first stage is done locally at the end user side but the second stage is done at remote nodes that can be donated by multiple non-colluding end users that requested the recommendations or third parties mash-up service. All the communications between participants are done through anonymised network to hide their network identity. In this paper, we also provide a mobile jukebox network scenario and experimentation results.