The current approaches to automatic identification of web services for a given set of requirements involve matching based on the interface information published by the service providers. However, due to concerns about exposing of internals of Web services, this information is typically limited, thus rendering Web service matching quite difficult in practice. In this paper, we argue that service matching can be significantly enhanced by harnessing the environmental information about the Web services. Towards this end, we explore two crucial questions: (i) what environmental information would improve service matching, and (ii) how much of that information can be revealed without violating the fundamental tenet of service-oriented architecture that the internal implementation details of Web services are not available to Web service consumers? This paper provides a precise characterization of environmental information of web services. We motivate our approach via real-life Web service search portals, by showing how environmental information can improve the precision and recall of service matching process. We then show how Web service providers can extract this information from the designs of the Web services, and publish them along with their interfaces. We illustrate our ideas with a realistic running example, and demonstrate it via a proof-ofconcept prototype.