Network Intrusion Detection Systems (NIDSs) have always been designed to enhance and improve the network security issue by detecting, identifying, assessing and reporting any unauthorized and illegal network connections and activities. The purpose of this research is to improve on the existing Anomaly Based Intrusion Detection (ABID) method using K-Means clustering technique as to maximize the detection rate and accuracy while minimizing the false alarm. The problem with outliers may disturb the K-Means clustering process as it might be avoided in the clustering process from mixing with the normal data that make the NIDSs become less accurate. Thus this research aims to improve the performance of the ABID systems that balance the loss of information or ignored data in clustering. An integrated machine learning algorithm using K-Means Clustering with discretization technique and Naïve Bayes Classifier (KMC-D+NBC) is proposed against ISCX 2012 Intrusion Detection Evaluation Dataset. The outcome depicts that the proposed method generates better detection rate and accuracy up to 99.3 and 99.5 respectively and reduces the false alarm to 1.2 with better efficiency of 0.03 seconds time taken to build model. © 2016 IEEE.