We propose an enhanced mechanism for selecting partners for multi-attribute negotiation. The mechanism employs possibilistic case-based reasoning. The possibility of successful negotiation for each potential partner is predicted on the basis of its behaviour in previous multi-attribute negotiations. The qualitative expected utility for each potential partner is derived and the agents are ordered according to the values of these utilities. The order determines who is more and who is less desirable partner for negotiation. The proposed approach allows choosing the most prospective negotiation partners based on small sample of historical cases of previous interactions even if the previous situations are different from the current one. A simple example of calculations is presented to demonstrate the proposed approach.