We present an agent-based and context-oriented approach for the composition of Web services. A Web service is an accessible application that other applications and humans can discover and trigger to satisfy multiple needs (e.g., hotel booking). Because of the complexity that characterizes the composition of Web services, two concepts in this paper are put forward to reduce this complexity namely software agent and context. A software agent is an autonomous entity that acts on behalf of users, whereas context is any relevant information that characterizes a situation. During the composition process, software agents engage conversations with their peers to agree on which Web services will participate in this process. In these conversations, agents take into account the execution context of the Web services.