Having precise specifications of service APIs is essential for many Software Engineering activities. Unfortunately, available documentation of services is often inadequate and/or imprecise and, hence, cannot be fully relied upon. Generating service documentation manually is a tedious and error-prone task, especially in light of changes to services. Therefore, there is a need for automated support in generating service documentation. In this work, we present a novel approach to infer the API of a service by analyzing recorded messages sent to and received from this service. Our approach includes a novel, two-level clustering technique to cluster messages, a step that many existing approaches to infer message formats fail to perform precisely in the presence of significant variation of payload information of the available messages. We have evaluated our approach on message traces from four different real-world services. The experimental result shows that our approach is more effective than existing techniques in extracting correct message formats from recorded messages.