E-commerce is expected to achieve high market penetration if coupled with the appropriate technologies. Mobile Agent Technology (MAT) may enhance the intelligence and improve the efficiency of systems in the e-marketplace. Such a highly competitive and extremely dynamic market should encompass mechanisms for enabling users (Buyers) to find the most appropriate service providers (Sellers), i.e., those offering adequate quality services at a certain time period in a cost efficient manner. In this study, the Buyers’ decision on the “best” Seller is based on a weighted combination of the evaluation of the quality of the Sellers’ offer (performance related factor) and of their reputation rating (reliability related factor). Efficient negotiation frameworks are enhanced with a Sellers’ collaborative reputation mechanism, which helps estimating their trustworthiness and predicting their future behaviour, taking into account the Sellers’ past performance in satisfying the Buyers’ expectations. In essence, Sellers are rated with respect to whether they honoured or not the agreements they have established with the Buyers, thus introducing the concept of trust among the negotiators. The reputation mechanism considers both first-hand information (acquired from the Buyer’s past experiences with the Sellers) and second-hand information (disseminated from other Buyers’ based on their own past experiences with the Sellers), while spurious reputation ratings are taken into account.