The network intrusion detection system is an important tool for protecting computer networks against threats and malicious attacks. Many techniques have recently been proposed; however, these techniques face significant challenges due to the continuous emergence of new threats that are not recognized by the existing detection systems. In this paper, we propose a novel two-stage deep learning model based on a stacked auto-encoder with a soft-max classifier for efficient network intrusion detection. The model comprises two decision stages: an initial stage responsible for classifying network traffic as normal or abnormal using a probability score value. This is then used in the final decision stage as an additional feature for detecting the normal state and other classes of attacks. The proposed model is able to learn useful feature representations from large amounts of unlabeled data and classifies them automatically and efficiently. To evaluate and test the effectiveness of the proposed model, several experiments are conducted on two public datasets: an older benchmark dataset, the KDD99, and a newer one, the UNSW-NB15. The comparative experimental results demonstrate that our proposed model significantly outperforms the existing models and methods and achieves high recognition rates, up to 99.996% and 89.134%, for the KDD99 and UNSW-NB15 datasets, respectively. We conclude that our model has the potential to serve as a future benchmark for deep learning and network security research communities.