We propose a composability model to ascertain that Web services can safely be combined, hence avoiding unexpected failures at runtime. Composability is checked through a set of rules organized into four levels: syntactic, static semantic, dynamic semantic, and qualitative levels. We introduce the concepts of composability degree and Ï-composability to cater for partial and total composability. We also propose a set of algorithms for checking composability. Finally, we conduct a performance study (analytical and experimental) of the proposed algorithms.