Being a fast-growing Internet application, Voice over Internet Protocol (VoIP) shares the network resources with the regular Internet traffic, and is susceptible to the existing security holes of the Internet. Moreover, given that voice communication is time sensitive and uses a suite of interacting protocols, VoIP exposes new forms of vulnerabilities to malicious attacks. In this paper, we propose a highlyneeded VoIP intrusion detection system. Our approach is novel in that, it utilizes not only the state machines of network protocols but also the interaction among them for intrusion detection. This detection approach is particularly suited for protecting VoIP applications, in which a melange of protocols are involved to provide IP telephony services. Based on tracking deviations from interacting protocol state machines, our solution shows promising detection characteristics and low runtime impact on the perceived quality of voice streams.