Most real-world negotiations involve multiple, interdependent issues or attributes. These negotiation scenarios are specially challenging because agents’ preferences on the attributes may be non-monotonic. The existing works in the area of non-monotonic preference scenarios are mainly restricted to mediated approaches and to very specific agents’ preference models. In this research we propose NegoExplorer, a generic framework for non-mediated automated bilateral multi-attribute negotiations. NegoExplorer is based on a region-based recursive bargaining mechanism. The mechanism is named recursive because agents negotiate on regions and not on specific contracts in the negotiation space, and because an agreement on a region implies a new bargaining which is constrained to that region. Agents may reach an agreement on a contract by iteratively applying this recursive mechanism. In order to evaluate the effectiveness of our proposal we have compared it with a classical similarity based negotiation protocol. The preliminary results are promising, showing better results in terms of utility and negotiation time for the case of non-monotonic and non-differentiable utility spaces, and similar results for monotonic spaces. We believe that the ideas presented in this paper may be the starting point of a new family of negotiation mechanisms.