A method and apparatus for invoking a service in a service-oriented architecture in which a client invokes such service from a service provider using a selected transport binding. A service binding for a service invocation from the service provider is first negotiated in a negotiation process using a first transport binding. The service invocation is then handled using the service binding negotiated in the negotiation process. A client may first determine whether a server is capable of negotiating a service binding. If the server is capable of negotiating a service binding, the client negotiates a service binding with the server. Otherwise, a service binding is selected on the basis on diagnostic information available to the client without negotiating with the server. Separate service bindings may be negotiated for each of several portions of a communication path, either by the client and service provider or by intermediaries along the communication path.