Negotiation is a decentralised decision-making process of finding efficient agreements between two or more partners in the presence of limited common knowledge and conflicting preferences. It is a key mechanism for distributing tasks, sharing resources, composing services and forming coalitions in multi-agent environments. In relatively small environments a self-interested agent can typically achieve its best results by negotiating with all agents that offer their services (also resources, capabilities etc) and then choosing an agreement or deriving a compound agreement that best satisfies its negotiation objectives (e.g. maximal payoff). However negotiation can be expensive in terms of the computational time and resources, and it can also be impractical to negotiate with a large number of agents, especially in open dynamic environments. More importantly it is always desirable to negotiate with the agents with whom there is a higher chance of successful negotiation and reaching better agreements. Therefore selection of most prospective partners for negotiation is of critical importance to the practicality and efficiency of multi-agent negotiation. We propose an approach for selecting partners in multi-agent negotiation with the use of possibilistic case-based reasoning. It enables to predict the possibility of successful negotiation with other agents based on their past negotiation behaviour and then derive qualitative expected utility for the current situation. The proposed approach allows the agents to select their most prospective negotiation partners based on a small sample of historical cases of previous negotiations even if they are different from the current situation.