In the service-oriented paradigm, Web service interfaces are considered contracts between Web service subscribers and providers. The structure of service interfaces has an extremely important role to discover, understand, and reuse Web services. However, it has been shown that service developers tend to pay little care to the design of their interfaces. A common design issue that often appears in real-world Web services is that their interfaces lack cohesion, i.e., they expose several operations that are often semantically unrelated. Such a bad design practice may significantly complicate the comprehension and reuse of the services functionalities and lead to several maintenance and evolution problems. In this paper, we propose a new approach for Web service interface decomposition using a Formal Concept Analysis (FCA) framework. The proposed FCA-based approach aims at identifying the hidden relationships among service operations in order to improve the interface modularity and usability. The relationships between operations are based on cohesion measures including semantic, sequential and communicational cohesion. The identified groups of semantically related operations having common properties are used to define new cohesive and loosely coupled service interfaces. We conducted a quantitative and qualitative empirical study to evaluate our approach on a benchmark of 26 real world Web services provided by Amazon and Yahoo. The obtained results show that our approach can significantly improve Web service interface design quality compared to state-of-the-art approaches.