As Web Services have matured they have been substantially leveraged within the academic, research and business communities. An exemplar of this is the realignment, last year, of the dominant Grid application framework — Open Grid Services Infrastucture (OGSI) — with the emerging consensus within the Web Services community. Reliable messaging is an important component within the Web Services stack. There are two competing, and very similar, specifications within this domain viz. WS-ReliableMessaging (WSRM) and WS-Reliability (WSR); this work focuses on the WSRM specification. In this paper we provide an overview of the WSRM protocol, describe our implementation of WSRM, and present an analysis of the costs (in terms of latencies and memory utilizations) involved in the use of WSRM. Since WSRM is very similar to WS-Reliability we expect the performance of WSRM to be very similar to that of WSR. We hope that the work presented here helps researchers and systems designers gauge the suitability of Web Services based reliable messaging in their applications and also to make appropriate trade-offs, which includes inter alia interoperability, guarantees, quality of service and performance.