A Web services-based publish/subscribe system has the potential to create an Internet scale interoperable event notification system which is important for Grid computing as it evolves a service-oriented architecture. WSMessenger is designed to be a Web services-based message broker that can decouple event producers and event consumers and achieve scalable, reliable and efficient message delivery. In this paper, we discuss some challenges that are unique to Web services-based publish/subscribe systems and the key features that distinguish WS-Messenger from other existing message brokers. We then present the architecture and the technology used in WS-Messenger. Performance tests indicate WS-Messenger performs better than the WSNotification implementation in Globus Toolkit 4 (GT4) and it can be used as a complement to GT4 to improve its scalability. We lastly describe its application to Grid workflow orchestration in the LEAD project.