The SOAP protocol has emerged as a Web Service communication standard, providing simplicity, robustness, and extensibility. SOAP's relatively poor performance threatens to limit its usefulness, especially for high-performance scientific applications. The serialization of outgoing messages, which includes conversion of in-memory data types to XML-based string format and the packing of this data into message buffers, is a primary SOAP performance bottleneck. We describe the design and implementation of differential serialization, a SOAP optimization technique that can help bypass the serialization step for messages similar to those previously sent by a SOAP client or previously returned by a SOAP-based Web Service. The approach requires no changes to the SOAP protocol. Our implementation and performance study demonstrate the technique's potential, showing a substantial performance improvement over widely used SOAP toolkits that do not employ the optimization. We identify several factors that determine the usefulness and applicability of differential serialization, present a set of techniques for increasing the situations in which it can be used, and explore the design space of the approach.