Though Web Services become more and more popular, not only inside closed intranets but also for inter-enterprise communications, few efforts have been made so far to secure a Web Service’s availability. Existing security standards like e.g. WS-Security only address message integrity and confidentiality, and user authentication and authorization. In this article we present a system for protecting Web Services from Denial-of-Service (DoS) attacks. DoS attacks often rely on misformed and/or overly long messages that engage a server in resource-consuming computations. Therefore, a suitable means to prevent such kinds of attacks is the full grammatical validation of messages by an application level gateway before forwarding them to the server. We discuss specific kinds of DoS attacks against Web Services, show how message grammars can automatically be derived from formal Web Service descriptions (written in the Web Service Description Language), and present an application level gateway solution called “Checkway” that uses these grammars to filter Web service messages. The paper closes by giving some performance figures for full grammatical validation.