In this paper, we present a novel deployment-time binding selection framework for Web services to improve the performance. Using the information about target environments, we determine the best binding based on the availability and the accessibility of a service, and the performance characteristics of the bindings in a target environment. We have implemented the proposed mechanism as part of Eclipse-based development tools. We present an extensive performance evaluation of our methodology using benchmarks that we have created following public Web service interfaces, and emulating several e-business applications including a large scale legacy transaction processing system that runs on a mainframe.