Algorithms and software for proactive and adaptive detection of network/service anomalies (i.e., performance degradations) have been developed, implemented, deployed, and field-tested for transaction-oriented wide area networks (WANs). A real-time anomaly detection system called TRISTAN (transaction instantaneous anomaly notification) has been implemented, and is deployed in the commercially important AT&T transaction access services (TAS) network. TAS is a high volume, multiple service classes, hybrid telecom and data WAN that services transaction traffic in the U.S. and neighboring countries. TRISTAN adaptively and preactively detects network/service performance anomalies in multiple-service-class-based and transaction-oriented networks, where performances of service classes are mutually dependent and correlated, where environmental factors (e.g., nonmanaged or nonmonitored equipment within customer premises) can strongly impact network and service performances. Specifically, TRISTAN implements algorithms that: 1) sample and convert raw transaction records to service-class based performance data in which potential network anomalies are highlighted; 2) automatically construct adaptive and service-class-based performance thresholds from historical transaction records for detecting network and service anomalies; and 3) perform real-time network/service anomaly detection. TRISTAN is demonstrated to be capable of proactively detecting network/service anomalies, which easily elude detection by the traditional alarm-based network monitoring systems.