The requirements regarding the rapid change in markets and business organisations towards a Future Internet foresee new interoperability demands and complexity levels, from connection and syntax-oriented exchanges to semantic and model-oriented knowledge. This change is not trivial and entails new problems and approaches beyond the scope of the available applications. The proposed solution to improve the robustness and sustainability of the Enterprise Interoperability to higher levels of abstraction and deeper knowledge has negotiation as its central mechanism. This paper proposes the main building blocks for implementing a negotiation framework for this purpose, which include the establishment of a Multi-agent System and of a flexible negotiation environment using a dedicated rule engine. The paper concludes with the definition of a prototype to prove the framework and some tests performed over it.