Web Services allow a user to integrate applications from different platforms and languages. Since mobile applications often run on heterogeneous platforms and conditions, Web Service becomes a popular solution for integrating with server applications. However, because of its verbosity, XML based SOAP messaging gives the possible overhead to the less powerful mobile devices. Based on the mobile client's behavior that it usually exchanges messages with Web Service continuously in a session, we design the Handheld Flexible Representation architecture. Our proposed architecture consists of three main components: optimizing message representation by using a data format language (Simple_DFDL), streaming communication channel to reduce latency and the Context-store to store context information of a session as well as redundant parts of the messages. In this paper, we focus on the Context-store and describe the architecture with the Context-store for improving the performance of mobile Web Service messaging. We verify our approach by conducting various evaluations and investigate the performance and scalability of the proposed architecture. The empirical results show that we save 40% of transit time between a client and a service by reducing the message size. In contrast to solutions for a single problem such as the compression or binarization, our architecture addresses the problem at a system level. Thus, by using the Context-store, we expect reliable recovery from the fault condition and enhancing interoperability as well as improving the messaging performance.