There are a multitude of benefits and challenges that can be derived from the convergence of two major current technologies: (a) Web services (WS) – technology that allows application development and integration using the service-oriented computing paradigm; and (b) E-business systems – using the Internet as the basis for interacting with customers, suppliers, and other business partners. This combination, called WS-based e-business systems promises to provide a dynamic e-business environment. We investigate the existing deployment barriers for such an environment from the perspectives of the three WS stakeholders, namely the service providers, service consumers and the WS Standards Organizations; and present a challenges framework that organizes and interrelate these barriers in an easily understandable manner to help study further the factors that impact the deployment and use of WS within e-business. Using this framework we analyze WS incorporation challenges for small and medium-sized enterprises (SMEs) since they are a vital engine driving the world economy, and are realizing significant benefits from adoption and implementation of Internet-based business solutions. WS-based e-business system applications promise to do even more for them.