Multimedia Web services constitute a considerable load on Internet bandwidth and on Web servers. With the increasing demand of multimedia Web services, the need to maintain a respectable QoS is a major concern for multimedia Web services’ providers. Binary data compression, lossy and lossless, increases performance gain and maintains QoS, at large and small-scale implementations. At the expense of increased CPU processing time, data compression provides a reliable solution to sustain QoS parameters such as response time, download time and server delay where bandwidth is limited.This paper presents a detailed analysis, which is based upon realistic and representative data, in order to quantify the performance gain for multimedia Web services due to the application of binary image compression. To provide data for our analysis method, we have built an image-retrieval Web service that provides a set of images in both compressed and non-compressed form. The work in this paper promotes the utilisation of multimedia compression techniques and proposes the integration of multimedia compression techniques in current Web standards such as HTTP.The analysis method and results can be extended and adapted to various service and network models, such as wireless LAN, Ad-Hoc, mobile networks, IP-telephony and distributed systems.