Network anomaly detection has been an active research topic in the field of Intrusion Detection for many years, however, it hasn’t been widely applied in practice due to some issues. The issues include high false alarm rate, limited types of attacks the approach can detect, and that such approach can’t perform real-time intrusion detection in high speed networks. This paper presents a network anomaly detector based on Dempster-Shafer (D-S) evidence theory. The detector fuses multiple features of network traffic to decide whether the network flow is normal, and by such fusion it achieves low false alarm rate and missing rate. It also incorporates some self-adaptation mechanisms to yield high accuracy of detection in dynamic networks. Furthermore, light-computation features are used to develop an efficient fusion mechanism to guarantee high performance of the algorithm. On the 1999 DARPA/Lincoln Laboratory intrusion detection evaluation data set, this detector detects 69% attacks at low false alarm rate. Such result is better than the 50% detection rate of EMERALD—the winner of 1999 DARPA/Lincoln Laboratory intrusion detection evaluation, and results from other research projects.