Web Services and Messaging, as application-toapplication communication paradigms, have so far been considered separately, with independent programming models and supporting middleware. Different efforts are now introducing messaging notions such as asynchrony, greater consumer cardinality, and looser coupling between web services. This trend will likely result in an extension of the web services programming model. It is not clear, however, that this extension will adhere to a pre-planned approach. A coherent approach requires a thorough integration of the web services and messaging paradigms. This paper proposes one such approach which, in addition to supporting the current style of web services interactions, allows the incorporation of messaging-style interactions under a common programming model. These messaging-style interactions include asynchronous request-response, oneway multi-consumer interactions, and even multiple-choice point-to-point interactions, common in message queuing systems. This paper also elaborates on a model for oneway multi-consumer interactions that integrates the publish/ subscribe mode of messaging into the web services programming model. A primary motivation for our approach is to take advantage of key messaging features, while exerting as small an impact as possible on the web services programming model.