Recently, as damage caused by Internet threats has increased significantly, one of the major challenges is to accurately predict the period and severity of threats. In this study, a novel probabilistic approach is proposed effectively to forecast and detect network intrusions. It uses a Markov chain for probabilistic modeling of abnormal events in network systems. First, to define the network states, we perform K-means clustering, and then we introduce the concept of an outlier factor. Based on the defined states, the degree of abnormality of the incoming data is stochastically measured in real-time. The performance of the proposed approach is evaluated through experiments using the well-known DARPA 2000 data set and further analyzes. The proposed approach achieves high detection performance while representing the level of attacks in stages. In particular, our approach is shown to be very robust to training data sets and the number of states in the Markov model.