The paper presents a network intrusion detection approach that flags malicious activity without previous knowl- edge about attacks or training data. The Cluster Change-Based Intrusion Detection approach (C2BID) detects intrusions by monitoring host behavior changes. For that purpose, C2BID defines and extracts features from network data, aggregates hosts with similar behavior using clustering, then analyses how hosts move between clusters along a period of time. This contrasts with previous work in the area that stops at the clustering step. We evaluated C2BID experimentally with two datasets, obtaining better F-Score than previous solutions.